Input Format
The first line contains an integer, , the number of test cases.
Each of the  subsequent lines contains an integer, , to be tested for primality.
Constraints
Output Format
For each test case, print whether  is  or  on a new line.

### Problem solution in Java programming language.

import java.util.*;

public class Solution {

static boolean isPrime(int n) {
for(int i=2;i<=Math.sqrt(n);i++) {
if(n%i==0) {
return false;
}
}
return true;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int numOfTests = sc.nextInt();
for (int i = 0; i < numOfTests; i++) {
int x = sc.nextInt();
String s;
if (x >= 2 && isPrime(x)) {
s = "Prime";
} else {
s = "Not prime";
}
System.out.println(s);
}
}
}

#### second solution

import java.util.*;

public class Solution {
/**
*   Improved O( n^(1/2)) ) Algorithm
*    Checks if n is divisible by 2 or any odd number from 3 to sqrt(n).
*    The only way to improve on this is to check if n is divisible by KNOWN PRIMES from 2 to sqrt(n).
*
*   @param n An integer to be checked for primality.
*   @return true if n is prime, false if n is not prime.
**/
public static boolean isPrime(int n){
// check lower boundaries on primality
if( n == 2 ){
return true;
} // 1 is not prime, even numbers > 2 are not prime
else if( n == 1 || (n & 1) == 0){
return false;
}

// Check for primality using odd numbers from 3 to sqrt(n)
for(int i = 3; i <= Math.sqrt(n); i += 2){
// n is not prime if it is evenly divisible by some 'i' in this range
if( n % i == 0 ){
return false;
}
}
// n is prime
return true;
}

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int testCases = scan.nextInt();
for(int i = 0; i < testCases; i++){
System.out.println(
(isPrime(scan.nextInt()) ? "Prime" : "Not prime") );
}
scan.close();
}
}

### Problem solution in Python programming language.

import math

def isPrime(n):
if n == 2:
return True
elif n == 1 or (n & 1) == 0:
return False

for i in range(2, math.ceil(math.sqrt(n)) + 1):
if (n % i) == 0:
return False

return True

p = int(input())
for i in range(0, p):
x = int(input())

s = "Prime" if (isPrime(x)) else "Not prime"
print(s);