Description

Whenever we think of sorting integers, we tend to think of sorting them in ascending or descending order. However, we can play around a bit and define new sorting criteria. One criterion could be sorting numbers in terms of their summation of digits. Therefore in this sorting criterion, 13 would come before 9 as sum of the digits of 13 is 4 and that of 9 is 9. In this problem, we are concerned with sorting numbers in the range 1 to 2000000 with the following sorting criteria. Numbers in this range must be sorted in terms of the number of factors in their prime factorization. Incase of a tie, the smaller number will come first. For example, 20 = 2*2*5, so it has 3 numbers in its prime factorization. Similarly 35 = 5*7 has 2 numbers in its prime factorization. Therefore, 35 will come before 20 according to this criterion.

Input

Each case of input will consist of a positive integer n<=2000000. The last case is followed by a 0. Total number of test cases can be as large as 100000.

Output

For each case of input, there will be one line of output. It will consist of the case number followed by the nth number in the range 1 to 2000000 after the sorting rule has been applied. Look at sample output for further clarification.

Sample Input

1 2 3 4 0

Sample Output

Case 1: 1 Case 2: 2 Case 3: 3 Case 4: 5

Source

Shamim Hafiz @ Next generation contest ĘC 4 @ UVA