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.

Input

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.

Example Input

1729
17
561
1109
431

Output

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

Example Output

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

Programming Challanges

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

Submission

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

$ cd path/to/cse-30872-fa22-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-fa22/challenge21
{"result": "Success", "score": 6, "time": 0.06403017044067383, "value": 6, "status": 0}

Pull Request

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.


  1. Chuck Bartowski. 

  2. If teaching this class doesn't work out, I'll probably end up there. 

  3. Chuck's handler. 

  4. Well in C++. In Python, it will do the right thing