MathNumber Theory
A prime number is greater than 1 and has no divisors other than 1 and itself. Decide whether n is prime.
Input
A single integer n.
Output
Print Prime or Not Prime.
Constraints
1 <= n <= 10^9
Example 1
Input
7
Output
Prime
7 is only divisible by 1 and 7.
Example 2
Input
12
Output
Not Prime
12 = 3 * 4, so it is not prime.