Assignment

Write a program that asks the user for a number, and then says whether that number is a prime number or not.

What are prime numbers?

A prime number is a positive integer that is divisible only by 1 and itself. The lowest (and only even) prime number is 2. The first 10 prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

(PS: the official definition is a bit more specific, making 1 not a prime number)



Examples

Example 1

Input

5

Output

5 is prime
Example 2

Input

21

Output

21 is not prime

(because 21 is also divisible by 3 and 7)

Example 3

Input

17

Output

17 is prime
Example 4

Input

55

Output

55 is not prime

(because 55 is also divisible by 5 and 11)