#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	if (!(cin >> t)) {
		return 0;
	}
	int m = 2;
	int k = 3;
	int o = 1;
	while (t--) {
		string s;
		cin >> s;
		int n = s.length();
		vector<int> v;
		int c = o;
		for (int i = o; i < n; i++) {
			if (s[i] == s[i - o]) {
				c++;
			} else {
				v.push_back(c);
				c = o;
			}
		}
		v.push_back(c);
		deque<int> q;
		for (int x : v) {
			q.push_back(x);
			while ((int)q.size() >= k && q[q.size() - m] >= m) {
				int a = q.back();
				q.pop_back();
				int b = q.back();
				q.pop_back();
				int d = q.back();
				q.pop_back();
				q.push_back(a + d);
			}
		}
		while (!q.empty()) {
			if (q.front() >= m) {
				q.pop_front();
			} else if (q.back() >= m) {
				q.pop_back();
			} else {
				break;
			}
		}
		if (q.empty()) {
			cout << "IGEN" << '\n';
		} else {
			cout << "NEM" << '\n';
		}
	}
	return 0;
}