Prime Number Check

A prime number is an integer greater than 1 whose only divisors are 1 and itself. 2, 3, 5 and 7 are prime; 1, 9 and 100 are not.

Given N, print Prime if it is prime, otherwise print Not Prime.

Be careful with the two special cases: 1 is not prime, and 2 is.

💡

Checking every number up to N is far too slow when N is near a billion. A divisor larger than the square root of N always pairs with one smaller than it, so testing up to sqrt(N) is enough.

Input

A single line containing one integer N.

Output

The word Prime or the words Not Prime.

Constraints

1 <= N <= 10^9

Example 1

Input

Output

Prime

Nothing between 2 and 6 divides 7.

Submit runs your code against 6 test cases — the 1 shown above plus 5 hidden ones covering the awkward cases. Run sample just tries the first example, which is usually what you want while you are still working it out.