Number Theory Episode 1 is going to be finished by this problem.How many times you can divide a even number by only prime numbers? And finally there will be no non-prime number.Just do it! OOpsss....also you have to find out the sum of all non-prime and prime divisiors.

Input

The first line will contain t (1<=t<=100) the testcases.

next each line will contain even number n<=10^14.

Its sure that answer must be exists.

Output

Findout the number of prime factors.Print prime numbers as lowest as possible.

Last line will print the sum of divisiors as the note has made.Print endline between two results.If there are no prime numbers print only the sum of all divisiors.

Example

Input:
3

8

32

56

Output:

2 3
2 3
Sum Of Divisiors: 15

2 5
Sum Of Divisiors: 63

2 3
7 1
Sum Of Divisiors: 120

Note: in second case For 32.We can say 32=2^5.So print 2 5.

and all the divisiors are 1 2 4 8 16 32 and sum of all are 63.

Sum Of Divisiors: 15

2 5
Sum Of Divisiors: 63

2 3
7 1
Sum Of Divisiors: 120
3 1
19 1
Sum Of Divisiors: 8