Migrated from Lutece 1472 Bob and Alice are playing factors

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

-Bob and his girl friend Alice like factors very much.

One day,Bob find a beautiful path : 4,2,1,Becauese 2 is the factor of 4 and 1 is the factor of 2.

Alice is excited,says"why can't we find a longest path A1,A2,A3....,Ak,A_{i+1} is the factor of A_{i} and A{i+1} < A_{i},for all 1<=i<k.

Bob is so stupid ,so can you answer this question?

And Bob also wants to know how many longest path he can get.

Input

First line is a positive integer T , represents there are T test cases.

For each test case:

First line includes one number A1(1≤A1≤1e18).

Output

For the i-th test case , first output Case #i: in a single line.

Then output the answer of i-th test case,the first answer is the length of the longest path and the second answer is the numbers of longest path.

Samples

1
4

Case #1: 3 1

Resources

“玲珑杯”ACM比赛 Round #2