#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> s;
		if (s.empty()) {
			cout << "IGEN" << '\n';
			continue;
		}
		vector<int> l;
		int cl = 1;
		for (int i = 1; i <= (int)s.length(); i++) {
			if (i < (int)s.length() && s[i] == s[i - 1]) {
				cl++;
			} else {
				l.push_back(cl);
				cl = 1;
			}
		}
		int k = (int)l.size();
		vector<bool> dp(k + 1, false);
		vector<int> h(2, -1);
		vector<int> f(2, -1);
		dp[0] = true;
		h[0] = 0;
		f[0] = 0;
		for (int j = 1; j <= k; j++) {
			if (j <= f[j % 2]) {
				dp[j] = true;
				h[j % 2] = j;
			}
			if (l[j - 1] >= 2) {
				for (int p = 0; p < 2; p++) {
					if (h[p] != -1) {
						int low = j - 1 - min(j - 1, k - j);
						if (h[p] >= low) {
							int m = j - h[p] - 1;
							int r = j + min(j - 1, k - j);
							int e = j + m;
							if (e <= r) {
								f[e % 2] = max(f[e % 2], r);
							}
						}
					}
				}
			}
			if (j <= f[j % 2]) {
				dp[j] = true;
				h[j % 2] = j;
			}
		}
		if (dp[k]) {
			cout << "IGEN" << '\n';
		} else {
			cout << "NEM" << '\n';
		}
	}
	return 0;
}