#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int liczba_testow;
    cin >> liczba_testow;
    int i, j;
    int czy_Pierwsza[liczba_testow];

    int tablica[liczba_testow];

    for(i=0; i<liczba_testow; i++) {
        cin >> tablica[i];

        for(j=2; j*j<=sqrt(tablica[i]); j++) {
            if(tablica[i]%j==0)
                czy_Pierwsza[i] = 0; // nie jest pierwsza
            else
                czy_Pierwsza[i] = 1; // jest pierwsza
        }
    }



    for(int l=0; l<liczba_testow; l++) {
        if(czy_Pierwsza[l] == 0)
            cout << "Liczba nie jest pierwsza!" << endl;
        else
            cout << "Liczba jest pierwsza!" << endl;
    }


    return 0;
}