int count = 0;
    cin >> count;
    
    for(int i = 0; i < count; i++)
    {
        int num;
        cin >> num;
        
        bool isPrime = true;
        if(num > 1)
        {
            for(int j = 2; j <= sqrt(num); j++)
            {
                if(num % j == 0)
                {
                    isPrime = false;
                    break;
                }
            }
        }
        else
            isPrime = false;
            
        if(isPrime)
            cout << "Prime" << endl;
        else
            cout << "Not prime" << endl;

bool isPrime(int n){
    bool prime = true;
    if (n<2)
        prime = false;
    else if(n%2==0 && n!=2)
        prime = false;
    else
    {
      for(int i=3;i<n;i+=2){
            if(n%i==0){
                prime=false;
                break;
            }
      }
    }
    return prime;            
}


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t,n;
    cin >> t;
    for(int i=0;i<t;i++){
        cin>>n;
        if(isPrime(n))
            cout<<"Prime"<<endl;
        else
            cout<<"Not prime"<<endl;
    }   
    
    return 0;
}

import math

def is_prime(n):
    if n <= 1:
        return "Not prime"
    if n == 2:
        return "Prime"
    if n % 2 == 0:
        return "Not prime"
    sqrt_n = int(math.sqrt(n))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return "Not prime"
    return "Prime"

T = int(input())
for _ in range(T):
    n = int(input())
    result = is_prime(n)
    print(result)

bool isPrime(int a){
    bool prime = true;
    if(a < 2)
        prime = false;
    else if(a == 2)
        prime = true;
    else if(a % 2 == 0)
        prime = false;
    // If a is divisible by some number smaller than its square root,
    // then it is not prime
    else{
        for(int i = 3; i <= sqrt(a); i += 2){
            if(a % i == 0){
                prime = false;
                break;
            }
        }
    }
    return prime;
}

int main(){
    int a = 0;
    int t = 0;
    bool prime = true;

    cin >> t;
    while(t-- > 0){
        cin >> a;
        prime = isPrime(a);
        if(prime)
            cout << "Prime" << endl;
        else
            cout << "Not prime" << endl;
    }

    return 0;
}

# Enter your code here. Read input from STDIN. Print output to STDOUT
t=int(input())
for _ in range(t):
    i=int(input())
    if i<=1:
        print('Not prime')
        
    elif i<=3:
        print('Prime')
        
    elif i%2==0 or i%3==0:
        print('Not prime')
    else:   
        n=5
        while n*n<=i:
            if i%n==0 or i%(n+2)==0:
                print('Not prime')
                break
            n+=6
        else:
            print('Prime')