Prime Digital Roots

Interview

Time limit2sMemory limit512 MB

Summary

For each number until 0, repeatedly sum its digits and stop early if a prime appears, then print the original and the prime digital root or none.

Level: Easy3 of 10
Topics: Math, Number theory, Simulation, Implementation
Solved: No attempts yet

Problem

The digital root of a number is found by adding together the digits that make up the number. If the resulting number has more than one digit, the process is repeated until a single digit remains.

Your task in this problem is to calculate a variation on the digital root: a prime digital root. The addition process described above stops when there is only one digit left, but it also stops if the original number, or any of the intermediate numbers formed by addition, is a prime number. If the process continues and results in a single digit that is not a prime number, then the original number has no prime digital root.

An integer greater than one is called a prime number if its only positive divisors are one and itself.

For example, the first six primes are 2, 3, 5, 7, 11, and 13.
The number 6 has four positive divisors: 6, 3, 2, and 1. Thus 6 is not prime.
Caveat: the number 1 is not prime.

Here are examples of prime digital roots:

1 is not a prime number, so 1 has no prime digital root.
3 is a prime number, so the prime digital root of 3 is 3.
4 is not a prime number, so 4 has no prime digital root.
11 is a prime number, so the prime digital root of 11 is 11.
642 is not a prime number, so adding its digits gives 6 + 4 + 2 = 12. This is not a prime number, so adding again gives 1 + 2 = 3. This is a prime number, so the prime digital root of 642 is 3.
128 is not a prime number, so adding its digits gives 1 + 2 + 8 = 11. This is a prime number, so the prime digital root of 128 is 11.
886 is not a prime number, so adding its digits gives 8 + 8 + 6 = 22. This is not a prime number, so adding again gives 2 + 2 = 4. This is not a prime number, so 886 has no prime digital root.

Input

The input contains a single integer on each line, in the range 0 to 999999 inclusive. The end of the input is indicated by the value 0.

Output

If the input number has a prime digital root, then the input number is output right aligned with a field width of 7. It is followed by a single space, and then by the calculated prime digital root, also right aligned with a field width of 7.

If the input number has no prime digital root, then the input number is output as defined above, followed by 4 spaces and then the word none in lowercase. The terminating zero is not output.

Examples1

Example 1

Input

Expected output

      1    none
      3       3
      4    none
     11      11
    642       3
    128      11
    886    none