X-factor Chains

Time Limit: 1000MS

Memory Limit: 65536K

Description

Given a positive integer X, an X-factor chain of length m is a sequence of integers,1 = X0, X1, X2, …, Xm = XsatisfyingXi < Xi+1 and Xi | Xi+1 where a | b means a perfectly divides into b.Now we are interested in the maximum length of X-factor chains and the number of chains of such length.

Input

The input consists of several test cases. Each contains a positive integer X (X ≤ 220).

Output

For each test case, output the maximum length and the number of such X-factors chains.

Sample Input

2
3
4
10
100

Sample Output

1 1
1 1
2 1
2 2
4 6

Hint

Source

POJ Monthly--2007.10.06, ailyanlu@zsu

提交代码