Problem C
GCD + LCM
Input: Standard Input

Output: Standard Output

Given the value of N, you will have to find the number of digits in G and L in base googol (). The definition of G and L are given below:

If you are not accustomed with the symbol , then for your kind information we give an example:

Here GCD(i,j) means the greatest common divisor of integer i and integer j, and LCM(i,j) means the Least Common Multiplicand of integer i and integer j.

Input

The input file contains at most 100 lines of inputs. Each line contains an integer N (1<N<1000001). Input is terminated by a line containing a single zero.

Output

For each line of input produce one line of output. This line contains the serial of output followed by two integers DG and DL. Here DG is the number of digits in G when written in base googol and DL is the number of digits in L when written in base googol. Don’t even think of submitting a brute force solution: It will probably take more than 2 years for the largest possible input. Look at the output for sample input for format details.

Sample Input Output for Sample Input

10 100 20000 0

Case 1: 1 1 Case 2: 11 146 Case 3: 494294 14972385

---

Problemsetter: Shahriar Manzoor

Special Thanks: Abdullah-al-Mahmud