King Martin is visiting Luinesia, where there are n different types of coins. He wants to collect the coins as many different types as he can. Now if King Martin wants to withdraw some money from HansLife Bank, the only bank available in Luinesia. The bank will give his money using this following algorithm.

    Let A be the amount of money to be withdrawn and B be the highest valued coin which value does not exceed A.

    withdraw (A)
    {
        if (A == 0) exit;
        Give the customer B valued coin.
        withdraw(A - B);
    }

King Martin have almost an infinite amount of money, so he can withdraw any amount of money from the bank. King Martin then asks you, as his servant and his trusted programmer and finance consultant, to count what is the maximum number of different coins he can collect in a single withdrawal.

Input

The first line of input contains of an integer T (1 ≤ T ≤ 10²), the number of test cases. Each of the test cases starts with n (0 ≤ n ≤ 10⁴), the number of different types of coin, followed by n integers denoting the value of each type of coin. It is guaranteed that each type of coin has unique value. The smallest value of coin in each test case will always be 1 and the largest value will not exceed 10⁹.

Output

For each case, print "Case #X: M", where X (1 ≤ X ≤ T) is the case number,and M is the maximum different coins he can collect in a single withdrawal. There must be no trailing spaces at the end of printed lines, neither empty characters. Print a newline after each testcase.

Example

Input:
2
6
1 2 4 8 16 32
6
1 3 6 8 15 20

Output:
Case #1: 6
Case #2: 4

Explanation

(For the sake of a tutorial problem XD)

Case 1: Suppose you withdraw coins with amount of 63, you can get all the coins by following the algorithm given.

Algorithm simulation:

• withdraw(63) → B(highest value coin that does not exceed A = 32) coin is given to customer. Call withdraw(63 - 32 = 31)
• withdraw(31) → B(highest value coin that does not exceed A = 16) coin is given to customer. Call withdraw(31 - 16 = 15)
• withdraw(15) → B(highest value coin that does not exceed A = 8) coin is given to customer. Call withdraw(15 - 8 = 7)
• withdraw(7) → B(highest value coin that does not exceed A = 4) coin is given to customer. Call withdraw(7 - 4 = 3)
• withdraw(3) → B(highest value coin that does not exceed A = 2) coin is given to customer. Call withdraw(3 - 2 = 1)
• withdraw(1) → B(highest value coin that does not exceed A = 1) coin is given to customer. Call withdraw(0)
• withdraw(0) → Exit

Ok. now look how many types coins do I get. Oh it's 6, with values 1, 2, 4, 8, 16 and 32.

Hope this clarifies your doubts folks! :D

(Note: Not doing the 2nd one. Do it by yourself :). Remember that king is infinitely rich, he can use any amount of money to be withdrawn! And only maximum type per single withdrawal is asked!)

(Hint: Read the tags. I did not write it just for decoration.