#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct B {
	int v, l, p, n;
	bool a;
};
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<B> v;
		v.reserve(s.length() + 10);
		int cv = s[0] - '0', cl = 1;
		for (int i = 1; i < (int)s.length(); i++) {
			if (s[i] - '0' == cv) {
				cl++;
			} else {
				v.push_back({cv, cl, (int)v.size() - 1, (int)v.size() + 1, true});
				cv = s[i] - '0';
				cl = 1;
			}
		}
		v.push_back({cv, cl, (int)v.size() - 1, -1, true});
		int h = 0, t = (int)v.size() - 1;
		queue<int> q;
		auto mid = [&](int i) {
			return v[i].a && v[i].p != -1 && v[i].n != -1;
		};
		for (int i = 0; i < (int)v.size(); i++) {
			if (mid(i) && v[i].l >= 2) {
				q.push(i);
			}
		}
		while (!q.empty()) {
			int i = q.front();
			q.pop();
			if (!mid(i) || v[i].l < 2) {
				continue;
			}
			int pr = v[i].p, nx = v[i].n;
			v[i].a = v[pr].a = v[nx].a = false;
			int nl = v[pr].l + v[nx].l, nv = v[pr].v, pp = v[pr].p, nn = v[nx].n;
			int idx = (int)v.size();
			v.push_back({nv, nl, pp, nn, true});
			if (pp != -1) {
				v[pp].n = idx;
			} else {
				h = idx;
			}
			if (nn != -1) {
				v[nn].p = idx;
			} else {
				t = idx;
			}
			if (mid(idx) && v[idx].l >= 2) {
				q.push(idx);
			}
		}
		while (h != -1) {
			if (v[h].l >= 2) {
				int nx = v[h].n;
				v[h].a = false;
				h = nx;
				if (h != -1) {
					v[h].p = -1;
				}
			} else if (v[t].l >= 2) {
				int pr = v[t].p;
				v[t].a = false;
				t = pr;
				if (t != -1) {
					v[t].n = -1;
				}
			} else {
				break;
			}
		}
		if (h == -1) {
			cout << "IGEN" << '\n';
		} else {
			cout << "NEM" << '\n';
		}
	}
	return 0;
}