Problem J
Prime Reduction

A prime number $p \geq 2$ is an integer which is evenly divisible by only two integers: 1 and $p$. A composite integer is one which is not prime. The fundamental theorem of arithmetic says that any integer $x$ can be expressed uniquely as a set of prime factors – those prime numbers which, when multiplied together, give $x$. Consider the prime factorization of the following numbers:

Consider the following process, which we’ll call prime reduction. Given an input $x$:

1. if $x$ is prime, print $x$ and stop

2. factor $x$ into its prime factors $p_1, p_2, \ldots , p_ k$

3. let $x = p_1 + p_2 + \cdots + p_ k$

4. go back to step 1

Write a program that implements prime reduction.

Input

Input consists of a sequence of up to $20\, 000$ integers, one per line, in the range $2$ to $10^9$. The number $4$ will not be included in the sequence (try it to see why it’s excluded). Input ends with a line containing only the number $4$.

Output

For each integer, print the value produced by prime reduction executed on that input, followed by the number of times the first line of the process executed.

2
3
5
76
100
2001
4

2 1
3 1
5 1
23 2
5 5
5 6