Description

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 will also stop if the original number, or any of the intermediate numbers (formed by addition) are prime numbers. 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. 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 will contain a single integer on each line in the range 0 to 999999 inclusive. The end of the input will be indicated by the value 0.

Output

If the input number has a prime digital root, then the input number must be output and followed by a single space, then by the calculated prime digital root. If the input number has no prime digital root, then the input number should be output as defined above followed by 1 space followed by the word none(in lowercase). The terminating zero should not be output.

Sample

Input

1
3
4
11
642
128
886
0

Output

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