Write a program that reads a sequence of natural numbers and, for each one, tells if it is a prime number or not. Remember that a natural number is prime if and only if it is greater than 1 and it does not have any positive divisor other than 1 and itself.

**Input**

Input consists of a number *n*,
followed by *n* natural numbers.

**Output**

For every given natural number, tell in a line if it is prime or not, following the format of the example.

**Hint**

For every given *n*,
at most about √*n* steps are needed
to know if it is prime or not.

Public test cases

**Input**

4 7 10 101 161

**Output**

7 is prime 10 is not prime 101 is prime 161 is not prime

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Java Python
- User solutions
- C C++ Java