Carmichael Numbers

암호 알고리즘 중에는 큰 소수를 활용하는 것도 있다. 하지만 어떤 큰 수가 소수인지를 판단하는 것은 그리 쉽지 않다.
페르마 테스트와 같이 빠른 속도로 매우 정확하게 소수 여부를 판단할 수 있는 확률적 소수 테스트 방법이라는 것이 있다. 소수 여부를 판단해야 할 정수 n이 주어졌을 때 a는 2이상 n-1이하의 난수라고 하자. 그러면 다음과 같은 식이 성립하면 n은 소수일 가능성이 있다.
a^n mod n = a
어떤 정수가 이러한 페르마 테스트를 여러 번 통과하면 그 정수는 소수일 가능성이 높다고 할 수 있다. 하지만 안 좋은 소식도 있다. 합성수(소수가 아닌 수) 중에는 그 수보다 작은 모든 정수에 대해 이 페르마 테스트를 통과하는 것도 있다. 이런 수를 카마이클 수라고 부른다.
주어진 정수가 카마이클 수인지 테스트하기 위한 프로그램을 만들어라.

입력은 여러 줄로 구성되며 각 줄에는 작은 양의 정수 n(2

입력된 각 수에 대해 아래에 있는 출력 예에 나와있는 식으로 그 수가 카마이클 수인지 아닌지를 판단한 결과를 출력하라.

~cpp 
1729
17
561
1109
431
0

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

작성자	사용언어	개발시간	코드
문보창	C++	3h 30m	CarmichaelNumbers/문보창
조현태	C	.	CarmichaelNumbers/조현태

----
문제분류 AOI