# Carmichael Numbers

Certain cryptographic algorithms make use of big prime numbers. However, checking
whether a big number is prime is not easy.

Randomized primality tests exist that offer a high degree of confidence of accurate
determination at a low cost, such as the Fermat test. Let *a* be a random number between
2 and *n* - 1 where *n* is the number whose primality we are testing. Then, *n* is
**probably** prime if the following equation holds:

a^{n} mod n = a

If a number passes the Fermat test several times, then it is prime with a high probability.

Unfortunately, there is bad news. Certain composite numbers (non-primes) still pass
the Fermat test with every number smaller than themselves. These numbers are called
Carmichael numbers.

Write a program to test whether a given integer is a Carmichael number.

## Input: carmichael.in

The input will consist of a series of lines, each containing a small positive number *n*
(2 ≤ n ≤ 65,000). A number *n* = 0 will mark the end of the input, and must not
be processed.

## Output: carmichael.out

For each number in the input, print whether it is a Carmichael number or not as shown
in the sample output.

## Sample Input

1729
17
561
1109
431
0

## Sample Output

1729 is a Carmichael number.
17 is normal.
561 is a Carmichael number.
1109 is normal.
431 is normal.