Prime Coprime Count

In this problem, you are given a list of positive integers. For each integer, if it is a prime number, you need to compute (\varphi(n)) which, for a prime number (n), is equal to (n-1). Otherwise, output "Not prime".

The function should process the list and output the results, one per line. Use standard input (stdin) for reading data and standard output (stdout) for writing results.

inputFormat

The first line contains a single integer (T) representing the number of test numbers. The second line contains (T) space-separated positive integers.

outputFormat

For each number in the input, output a line: if the number is not prime, print "Not prime"; if the number is prime, print "Prime X" where (X = n-1) which is the count of positive integers less than (n) that are coprime with (n) (i.e., (\varphi(n))).## sample

4
5 8 13 21

Prime 4
Not prime
Prime 12
Not prime