3421 -- X-factor Chains

Online Judge

Problem Set

Authors

Online Contests

User

Language:

X-factor Chains

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 12327		Accepted: 3946

Description

Given a positive integer X, an X-factor chain of length m is a sequence of integers,

1 = X₀, X₁, X₂, …, X_m = X

satisfying

X_i < X_i₊₁ and X_i | X_i₊₁ 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 ≤ 2²⁰).

Output

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

Sample Input

Sample Output

Source