// UUID: 4ab20234-48e6-4df4-8a99-48b73456eb15
#include <bits/stdc++.h>
using namespace std;
void solve()
{
	string s; cin>>s;
	vector<int> v{0};
	int curr=1;
	for(int i=1; i<s.size(); i++)
	{
		if(s[i]!=s[i-1])
		{
			v.push_back(min(curr,2));
			curr=0;
		}
		curr++;
	}
	int n=v.size();
	v.push_back(min(curr,2));
	array<int, 2> egy,ket;
	egy[0]=egy[1]=0;
	ket[0]=n+100,ket[1]=0;
	int db1=0,db2=0;
	for(int i=1; i<=n; i++)
	{
		if(v[i]==1) db1++;
		else db2++;
	}
	/*for(int i=1; i<=n; i++)
		cout<<v[i]<<" ";
	cout<<endl;*/
	for(int i=1; i<=n; i++)
	{
		array<int, 2> uj1{n+100,0},uj2{n+100,0};
		if(v[i]==1)
		{
			if(ket[0]<=ket[1]) uj1[0]=ket[0]+2,uj1[1]=ket[1]+2;
			if(egy[0]<=egy[1]) uj1[0]=min(uj1[0],egy[0]+1),uj1[1]=max(uj1[1],egy[1]+1);
			if(ket[0]<=ket[1] && ket[1]>0)
			{
				uj2[0]=max(0,ket[0]-1);
				uj2[1]=ket[1]-1;
			}
		}
		else
		{
			if(ket[0]<=ket[1] && ket[1]>0)
			{
				uj2[0]=max(0,ket[0]-1);
				uj2[1]=ket[1]-1;
			}
			//ha nem toroljuk ki
			if(ket[0]<=ket[1]) uj2[0]=min(uj2[0],ket[0]+1),uj2[1]=max(uj2[1],ket[1]+1);
			if(egy[0]<=egy[1]) uj2[0]=min(uj2[0],egy[0]),uj2[1]=max(uj2[1],egy[1]);
			if(egy[0]<=egy[1]) uj1[0]=egy[0],uj1[1]=egy[1];
			if(ket[0]<=ket[1]) uj1[0]=min(uj1[0],ket[0]+1),uj1[1]=max(uj1[1],ket[1]+1);
		}
		ket=uj2,egy=uj1;
		//cout<<i<<": "<<ket[0]<<" "<<ket[1]<<" "<<endl;
	}
	cout<<(ket[0]<=ket[1] && ket[0]<=0?"IGEN\n":"NEM\n");
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	int t=1; cin>>t;
	while(t--) solve();
}