|
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 10000.
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 |
Output for Sample
Input |
|
1 |
Case 1: 1 |
ProblemSetter:
Shamim Hafiz