Once again, agent Charles Carmichael ^{1} has been captured by the rogue
enemy spies. Fortunately, he has left clues about his location with the
Nerd Herd at the Buy More ^{2}. Being the geek that he is though, agent
Carmichael has encoded his information as a series of numbers.

Your mission as a top secret data analyzer is to crack the code! Being the clever and diligent programmer that you are, you have figured out that the stream of integers contains a particular type of numbers: Carmichael numbers!

These are composite numbers (non-primes) that pass the following prime test for
all numbers smaller than `n`

:

```
a^n mod n = a # Fermat test
```

That is let `a`

be a random number between `2`

and `n - 1`

, where `n`

is
the number we are testing. `n`

is probably a prime if it passes the
Fermat primality test several times. As noted, however, there are some
composite (non-primes) that also pass this test for all numbers less than
`n`

. These numbers, of course, are called Carmichael numbers and your job
is to help agent Walker ^{3} filter the list of numbers and determine which
ones are Carmichael numbers.

**Hint**: Simply computing `a^n mod n = a`

will lead to an overflow ^{4}.
Instead, you will need to manually perform modular exponentiation.

The input will consist of a series of lines, each containing a small
positive number `n`

where `(2 < n < 65,000)`

. You should read until the
*end-of-file*.

```
1729
17
561
1109
431
```

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

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

This is based on 10006 - Carmichael Numbers problem on the UVa Online Judge.

To submit your work, follow the same procedure you used for Reading 00:

```
$ cd path/to/cse-30872-fa24-assignments # Go to assignments repository
$ git checkout master # Make sure we are on master
$ git pull --rebase # Pull any changes from GitHub
$ git checkout -b challenge21 # Create and checkout challenge21 branch
$ $EDITOR challenge21/program.py # Edit your code
$ git add challenge21/program.py # Stage your changes
$ git commit -m "challenge21: done" # Commit your changes
$ git push -u origin challenge21 # Send changes to GitHub
```

To check your code, you can use the `.scripts/check.py`

script or curl:

```
$ .scripts/check.py
Checking challenge21 program.py ...
Result Success
Time 0.06
Score 6.00 / 6.00
$ curl -F source=@challenge21/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa24/challenge21
{"result": "Success", "score": 6, "time": 0.06403017044067383, "value": 6, "status": 0}
```

Once you have committed your work and pushed it to GitHub, remember to
create a **pull request** and assign it to the appropriate **teaching
assistant** from the Reading 11 TA List.