#include <bits/stdc++.h>
#define MAXN 201000
using namespace std;
int n,t,cnt;
char pch;
string ANS[2];
struct block
{
	bool nb;
	bool val;	
};
vector<block> blocks;
bool RX(int l,int r)
{
	if((l+r)%2==1)return 0;
	else if(blocks[(l+r)/2].nb==1) return 1;
	return 0;
}
bool RZ(int l,int r)
{
	if(blocks[l].val==0 && RX(l,r)==1)return 1;
	if(RX(l+1,r)==1 && blocks[l].val==0) return 1;
	if(RX(l,r-1)==1 && blocks[r].val==0) return 1;
	return 0;
}
bool RE(int l,int r)
{
	if(blocks[l].val==1 && RX(l,r)==1)return 1;
	if(RX(l+1,r)==1 && blocks[l].val==1) return 1;
	if(RX(l,r-1)==1 && blocks[r].val==1) return 1;
	return 0;
}
int main()
{
	ANS[0]="NEM\n";
	ANS[1]="IGEN\n";
	cin>>t;
	while(t--)
	{
		blocks.clear();
		cnt=0;
		string s;
		cin>>s;
		s+='-';
		pch='-';
		for(char ch:s)
		{
			if(ch!=pch)
			{
				block b;
				if(cnt>1) b.nb=1;
				else b.nb=0;
				
				if(pch=='0')b.val=0;
				else b.val=1; 
				cnt=1;
				if(pch!='-')blocks.push_back(b);
				pch=ch;
			}
			else cnt++;
		}
		n=blocks.size();
		bool ans=RX(0,n-1);
		for(int i=0;i<n;i++)
		{
			if(RZ(0,i) && RZ(i+1,n-1)) ans=1;
			if(RE(0,i) && RE(i+1,n-1)) ans=1;
			if(RX(0,i) && RX(i+1,n-1)) ans=1;
		}
		if(ans==1) cout<<"IGEN\n";
		else cout<<"NEM\n";
	}
	return 0;
}