#include <iostream>

using namespace std;

int main()
{
    int iloscliczb;
    cin >> iloscliczb;
    int *tab = new int[iloscliczb];

    //wczytywanie liczb do tablicy
    for (int i = 0; i < iloscliczb; i++){
        cin >> tab[i];
    }

    //wyszukiwanie max w tablicy
    int max = tab[0];
    for (int i = 0; i < iloscliczb; i++){
        if (max < tab[i]){
            max = tab[i];
        }
    }

    bool *liczbypierwsze = new bool [max + 1];

    // zapełnienie tablic indeksowaniej od maxa (bo tyle najwięcej będzie wartości)
    for (int i = 0; i <= max  ; i++){
        liczbypierwsze[i] = false;
    }

    //wpisywanie false gdy indeks i nie jest pierwszy
    for (int i = 2; i <= max + 1 ; i++){
        int k = 2;
        if (liczbypierwsze[i] == false){
            while(k*i <= max + 1){
                liczbypierwsze[k*i] = true;
                k = k + 1;
            }
        }
    }

   for (int i = 0; i < iloscliczb; i++){
        if(liczbypierwsze[tab[i]] == false) cout << "T" << endl;
        else cout << "N" << endl;
    }


    return 0;
}