Prime Factorization is the process of decomposing a number into all of its primes factors. For example, the prime factorization of 140 is 2 x 2 x 5 x 7. An interesting property that can arise from prime factorization is what happens when you add the factors instead of multiply them. Repeating this process for each sum eventually makes the factorization collapse into a single prime number. Given a non-prime integer greater than 5, print the sum of its prime factors, then iterate this process for each new sum until it collapses into a single prime number, lastly printing the amount of iterations.

Note: If adding the prime factors immediately leads to a prime on the first iteration, simply print the prime and print 1, since it ended after 1 factorization.

Input Specification

The only line of input is a non-prime integer ~N (6 \le N \le 10^7)~.

It is guaranteed that there will be no prime inputs.

Output Specification

Print each sum of the prime factors, then print the amount of iterations on a new line.

Sample Input

74

Sample Output

39 16 8 6 5 
5

Sample Explanation

The number 74 is inputted. The prime factorization of 74 is 2 x 37. Add these factors, you get 2 + 37 = 39.

Repeat this process. The prime factorization of 39 is 3 x 13. Add these factors, you get 3 + 13 = 16.

The prime factorization of 16 is 2 x 2 x 2 x 2. Add these factors, you get 2 + 2 + 2 + 2 = 8.

The prime factorization is 8 is 2 x 2 x 2. Add these factors, you get 2 + 2 + 2 = 6.

The prime factorization of 6 is is 3 x 2. Add these factors, you get 3 + 2 = 5.

Since 5 is a prime number, it can no longer be prime factorized. This is when the sequence ends, and the number 5 is printed on a new line, representing the amount of iterations of this process.

Sample Input 2

5262

Sample Output 2

882 22 13 
3

Sample Explanation 2

The number 5262 is inputted. The prime factorization of 74 is 2 x 3 x 877. Add these factors, you get 2 + 3 + 877 = 882.

The prime factorization of 882 is 2 x 3 x 3 x 7 x 7. Add these factors, you get 2 + 3 + 3 + 7 + 7 = 22.

The prime factorization of 22 is 2 x 11. Add these factors, you get 2 + 11 = 13

13 is a prime number and can no longer be factorized, thus the sequence ends and the number 3 is printed on a new line, again representing the number of iterations.