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 Python Rust