#include <bits/stdc++.h>

using namespace std;

int n, hossz;

int kezdo(int hely){
    int ki;
    int elotte = hely;
    int utana = hossz-1 - hely;

    return max(0, hely-min(elotte, utana));
}

int vegzo(int hely){
    int ki;
    int elotte = hely;
    int utana = hossz-1 - hely;

    return min(hossz-1, hely+min(elotte, utana));
}

bool megold(int akt, vector<int>& helyek, vector<int>& dp){
    if(vegzo(helyek[akt]) == hossz-1){
        return true;
    }

    if(dp[akt] != -1){
        return dp[akt];
    }

    bool ki = false;

    for(int i = akt+1; i < n; i++){
        if(vegzo(helyek[akt]) < helyek[i] &&
            vegzo(helyek[akt])+1 >= kezdo(helyek[i]) &&
            helyek[akt] < kezdo(helyek[i])){

            ki |= megold(i, helyek, dp);
        }
    }

    //cout << akt << " " << helyek[akt] << " " << (ki ? "lehet" : "nem lehet") << "\n";
    dp[akt] = ki;
    return ki;
}

void solve(){
    string s;
    cin >> s;
    s += 'x';
    vector<bool> blokkok;
    int h = 0;
    for(int i = 0; i < s.size()-1; i++){
        h++;
        if(s[i] != s[i+1]){
            blokkok.push_back((h > 1 ? 1 : 0));
            h = 0;
        }
    }
    hossz = blokkok.size();
    vector<int> helyek;
    for(int i = 0; i < blokkok.size(); i++){
        if(blokkok[i]){
            helyek.push_back(i);
        }
    }
    n = helyek.size();
    vector<int> dp(n, -1);
    bool lehet = false;
    for(int i = 0; i < n; i++){
        //cout << "index: " << i << " hely: " << helyek[i] << " kezdo: " << kezdo(helyek[i]) << " vegzo: " << vegzo(helyek[i]) << "\n";
        if(kezdo(helyek[i]) == 0){
            //cout << "indit " << i << " " << helyek[i] << "\n";
            lehet |= megold(i, helyek, dp);
        }
    }

    cout << (lehet ? "IGEN\n" : "NEM\n");

}

int main()
{
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}