Prime check

Problem

A security tool uses prime numbers. A prime number is a whole number greater than 1 that has no divisors other than 1 and itself.

Given n, print Prime if n is prime, otherwise Not prime.

Example 1

Input

Output

Prime

Example 2

Input

Output

Not prime

Try the problem first. Open one hint at a time.

Hint 1

Handle n below 2 first. Then try the divisors from 2 upwards.

Hint 2

You only need to try divisors up to the square root of n. A for loop with else fits well: the else runs when no divisor was found.

Write your Python code, run it on the examples and submit it to hidden tests.