A prime number is a positive integer that is divisible by exactly two different numbers, namely 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

### Input

An integer $$n \in \mathbb{N}_0$$.

### Output

A sentence that indicates if $$n$$ is a prime.

#### Tip

In a loop where you test the possible dividers of the number, you can conclude that the number is not prime as soon as you encounter a number other than 1 or itself that divides it. However, you can only conclude that it actually is prime after you have tested all possible dividers.

### Example

#### Input:

11


#### Output:

11 is a prime


### Example

#### Input:

12


#### Output:

12 is not a prime