#include <bits/stdc++.h>
using namespace std;

void solve() {
	string s;
	cin >> s;
	int n = s.length();
	vector<int> l;
	int cur = 1;
	for (int i = 1; i < n; i++) {
		if (s[i] == s[i - 1]) {
			cur++;
		} else {
			l.push_back(cur);
			cur = 1;
		}
	}
	l.push_back(cur);
	int k = l.size();
	vector<vector<pair<int, int>>> dp(k + 1);
	int mn = -1, mx = -1;
	for (int i = 0; i < k; i++) {
		if (l[i] >= 2) {
			if (mn == -1) {
				mn = i + 1;
			}
			mx = i + 1;
		} else if (mn != -1) {
			dp[k].push_back({mn, mx});
			mn = -1;
			mx = -1;
		}
	}
	if (mn != -1) {
		dp[k].push_back({mn, mx});
	}
	for (int i = k; i >= 1; i--) {
		if (dp[i].empty()) {
			continue;
		}
		sort(dp[i].begin(), dp[i].end());
		vector<pair<int, int>> merged;
		for (auto p : dp[i]) {
			if (merged.empty() || p.first > merged.back().second + 1) {
				merged.push_back(p);
			} else {
				merged.back().second = max(merged.back().second, p.second);
			}
		}
		if (i <= 2) {
			cout << "IGEN" << "\n";
			return;
		}
		for (auto p : merged) {
			int lv = p.first, rv = p.second;
			int il = max(lv, 2), ir = min(rv, i - 1);
			if (il <= ir) {
				dp[i - 2].push_back({il - 1, ir - 1});
			}
			if (lv == 1 && rv > 1) {
				dp[i - 1].push_back({1, rv - 1});
			}
			if (rv == i && lv < i) {
				dp[i - 1].push_back({lv, i - 1});
			}
		}
		dp[i].clear();
		vector<pair<int, int>>().swap(dp[i]);
	}
	cout << "NEM" << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}