Table of Contents

Prelude to Carmichael Numbers -- Primality Testing

First, start by reading the problem statement for Carmichael Numbers.

For this prelude, you are to test the primality of the input numbers.

Input

Input consists of a sequence of integers, n, 2 < n < 65000, one per line. The last entry is a 0, which should not be processed.

Output

For each non-zero input value, n, determine whether n is prime, then print n, a space, and either <tt>is prime.</tt> or <tt>is not prime.</tt>.

Sample Input

7
10
0

Sample Output

7 is prime.
10 is not prime.