Prime number check

Problem

A prime number is a whole number greater than 1 that divides exactly only by 1 and itself. Read n and print Prime or Not prime.

n can be as large as 2 billion, so trying every divisor up to n is too slow. Stop at the square root.

Example 1

Input

Output

Prime

No number from 2 to 5 divides 29.

Example 2

Input

Output

Not prime

1 is not prime.

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

Hint 1

If n has a divisor bigger than √n, it also has one smaller than √n. So only test i while i * i <= n.

Hint 2

Stop with break at the first divisor you find.

Hint 3

i * i can pass the int limit when n is near 2 billion, so make i a long.

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