False Ordering

We define b is a Divisor of a number a if a is divisible by b. So, the divisors of 12 are 1, 2, 3, 4, 6, 12. So, 12 has 6 divisors.

Now you have to order all the integers from 1 to 1000. x will come before y if

1)                  number of divisors of x is less than number of divisors of y

2)                  number of divisors of x is equal to number of divisors of y and x > y.

Input

Input starts with an integer T (≤ 1005), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 1000).

Output

For each case, print the case number and the n^th number after ordering.

Sample Input

5

1

2

3

4

1000

Sample Output

Case 1: 1

Case 2: 997

Case 3: 991

Case 4: 983

Case 5: 840

分析：题目大意是让你对1到1000的数按照题目给出的规则进行排序，根据每个数因子数多少，少的在前面，如果相等，大的在前面，因此自然想到使用comparator自定义比较器，简单易懂，上代码：

import java.util.*; public class Main{ static Scanner in=new Scanner(System.in); static List<num> a = new ArrayList<num>(); static Comparator<num> com = new Comparator<num>() { @Override public int compare(num o1, num o2) { if(o1.div==o2.div) return o2.i-o1.i; else return o1.div-o2.div; } }; static int fun(int num){ int sum = 0; int n = 1; while(n!=num){ if(num%n==0) sum++; n++; } return sum+1; } static void solve(){ for (int i = 1; i <= 1000; i++) { num n = new num(); n.i = i; n.div = fun(i); a.add(n); } Collections.sort(a, com); } public static void main(String args[]){ solve(); int k=in.nextInt(); int ca = 0; while(k-->0){ ca++; int n = in.nextInt(); System.out.println("Case "+ca+": "+ a.get(n-1).i ); } } } class num{ int i; int div; }