#include <bits/stdc++.h>

using namespace std;

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 c = 1;
		for (int i = 1; i < (int)s.size(); i++) {
			if (s[i] == s[i - 1]) {
				c++;
			} else {
				l.push_back(c);
				c = 1;
			}
		}
		l.push_back(c);
		int k = (int)l.size();
		vector<int> pr(k), nx(k);
		for (int i = 0; i < k; i++) {
			pr[i] = i - 1;
			nx[i] = i + 1;
		}
		nx[k - 1] = -1;
		vector<int> removed(k, 0);
		queue<int> iq, eq;
		auto check = [&](int i) {
			if (i == -1 || removed[i] || l[i] < 2) {
				return;
			}
			if (pr[i] != -1 && nx[i] != -1) {
				iq.push(i);
			} else {
				eq.push(i);
			}
		};
		for (int i = 0; i < k; i++) {
			check(i);
		}
		int kl = k;
		while (!iq.empty() || !eq.empty()) {
			if (!iq.empty()) {
				int i = iq.front();
				iq.pop();
				if (removed[i] || l[i] < 2 || pr[i] == -1 || nx[i] == -1) {
					continue;
				}
				int p = pr[i], n = nx[i];
				l[p] += l[n];
				removed[i] = 1;
				removed[n] = 1;
				kl -= 2;
				int nn = nx[n];
				nx[p] = nn;
				if (nn != -1) {
					pr[nn] = p;
				}
				check(p);
				if (nn != -1) {
					check(nn);
				}
			} else {
				int i = eq.front();
				eq.pop();
				if (removed[i] || l[i] < 2 || (pr[i] != -1 && nx[i] != -1)) {
					continue;
				}
				removed[i] = 1;
				kl -= 1;
				if (pr[i] == -1) {
					int n = nx[i];
					if (n != -1) {
						pr[n] = -1;
						check(n);
					}
				} else {
					int p = pr[i];
					if (p != -1) {
						nx[p] = -1;
						check(p);
					}
				}
			}
			if (kl == 0) {
				break;
			}
		}
		if (kl == 0) {
			cout << "IGEN" << '\n';
		} else {
			cout << "NEM" << '\n';
		}
	}
	return 0;
}