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

void solve() {
	string s;
	if (!(cin >> s)) {
		return;
	}
	int n = s.length();
	if (n == 0) {
		cout << "IGEN" << "\n";
		return;
	}
	vector<int> l;
	int c = 1;
	for (int i = 1; i < n; i++) {
		if (s[i] == s[i - 1]) {
			c++;
		} else {
			l.push_back(c);
			c = 1;
		}
	}
	l.push_back(c);
	vector<int> v;
	for (int x : l) {
		v.push_back(x);
		while (v.size() >= 3 && v[v.size() - 2] >= 2) {
			int a = v.back();
			v.pop_back();
			v.pop_back();
			v.back() += a;
		}
	}
	int head = 0, tail = (int)v.size() - 1;
	while (head <= tail) {
		if (v[head] >= 2) {
			head++;
		} else if (v[tail] >= 2) {
			tail--;
		} else {
			break;
		}
	}
	if (head > tail) {
		cout << "IGEN" << "\n";
	} else {
		cout << "NEM" << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	if (!(cin >> t)) {
		return 0;
	}
	while (t--) {
		solve();
	}
	return 0;
}