#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;
		vector<int> l;
		if (!s.empty()) {
			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;
		for (int i = 1; i < k - 1; i++) {
			if (l[i] >= 2) {
				q.push(i);
				in_q[i] = 1;
			}
		}
		while (!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_idx = pr[i];
			int n_idx = nx[i];
			l[p_idx] += l[n_idx];
			removed[i] = 1;
			removed[n_idx] = 1;
			int nn_idx = nx[n_idx];
			nx[p_idx] = nn_idx;
			if (nn_idx != -1) {
				pr[nn_idx] = p_idx;
			}
			if (pr[p_idx] != -1 && nx[p_idx] != -1 && l[p_idx] >= 2) {
				if (!in_q[p_idx]) {
					q.push(p_idx);
					in_q[p_idx] = 1;
				}
			}
		}
		int curr = -1;
		for (int i = 0; i < k; i++) {
			if (!removed[i]) {
				curr = i;
				break;
			}
		}
		if (curr == -1) {
			cout << "IGEN" << '\n';
			continue;
		}
		int tail = -1;
		for (int i = k - 1; i >= 0; i--) {
			if (!removed[i]) {
				tail = i;
				break;
			}
		}
		while (curr != -1 && (l[curr] >= 2 || l[tail] >= 2)) {
			if (l[curr] >= 2) {
				curr = nx[curr];
			} else if (l[tail] >= 2) {
				tail = pr[tail];
			}
		}
		if (curr == -1) {
			cout << "IGEN" << '\n';
		} else {
			cout << "NEM" << '\n';
		}
	}
	return 0;
}