Mr. Azad and His Son

There are a lot of people named Abul Kalam Azad in Bangladesh. But why is he so special? Being my dad is not the only reason. He can wonderfully do some calculations. If anyone gives him any positive integer k, he amazingly can say the relative perfect number 2^k – 1(2^k – 1) without using a calculator or a computer. (A perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself.) Say, I have told him to find out the relative perfect number of 2. He replies with 6, which is indeed a perfect number. But finding a relative perfect number of an integer is not always possible. I have asked him the process, but he says that I should find out by myself how an integer is related to a perfect number. Anyway, I have challenged him as it is very possible for me to do the same calculation using a computer. Although I could not figure out how he can do this, I know that the next ACM Online Programming Contest is near at hand, and the world's top programmers are available to solve my very simple problem.

Now, you are to write a program for me to help win over my dad. The program should take an integer n as input and determine its relative perfect number p.

Input Specification

Each line of the input consists of an integer 1 < n ≤ 31. The input is terminated by a line containing the number 0. This line should not be processed.

Output Specification

For each input line, the output will be in the following format:

• If a relative perfect number of n exists, then print “Perfect: p!”
• If a relative perfect number of n does not exist, and n is prime, then print “Given number is prime. But, NO perfect number is available.”
• If a relative perfect number of n does not exist, and n is not prime, then print “Given number is NOT prime! NO perfect number is available.”

Sample Input

1. 2
2. 3
3. 6
4. 0

download as text file

Output for Sample Input

1. Perfect: 6!
2. Perfect: 28!
3. Given number is NOT prime! NO perfect number is available.

download as text file