#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 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 = 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> in_q(k, 0), removed(k, 0);
		queue<int> q;
		auto add_to_q = [&](int i) {
			if (i > 0 && nx[i] != -1 && l[i] >= 2 && !in_q[i]) {
				q.push(i);
				in_q[i] = 1;
			}
		};
		for (int i = 1; i < k - 1; i++) {
			add_to_q(i);
		}
		int head = 0, tail = k - 1;
		while (true) {
			if (!q.empty()) {
				int i = q.front();
				q.pop();
				in_q[i] = 0;
				if (removed[i] || pr[i] == -1 || nx[i] == -1 || l[i] < 2) {
					continue;
				}
				int p = pr[i], n = nx[i];
				l[p] += l[n];
				removed[i] = 1;
				removed[n] = 1;
				int nn = nx[n];
				nx[p] = nn;
				if (nn != -1) {
					pr[nn] = p;
				} else {
					tail = p;
				}
				add_to_q(p);
				add_to_q(pr[p]);
				continue;
			}
			if (head != -1 && l[head] >= 2) {
				removed[head] = 1;
				int n = nx[head];
				if (n != -1) {
					pr[n] = -1;
					head = n;
					add_to_q(head);
				} else {
					head = -1;
					tail = -1;
				}
				continue;
			}
			if (tail != -1 && l[tail] >= 2) {
				removed[tail] = 1;
				int p = pr[tail];
				if (p != -1) {
					nx[p] = -1;
					tail = p;
					add_to_q(tail);
				} else {
					head = -1;
					tail = -1;
				}
				continue;
			}
			break;
		}
		if (head == -1) {
			cout << "IGEN" << '\n';
		} else {
			cout << "NEM" << '\n';
		}
	}
	return 0;
}