COLCOIN - Collecting Coins


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 ≤ 102), the number of test cases. Each of the test cases starts with n (0 ≤ n ≤ 104), 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 109.

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.


hide comments
aknov711: 2020-08-12 17:42:29

what is test case 15??
Getting WA on it!

Last edit: 2020-08-12 17:42:53
harshwardhan26: 2019-10-14 12:34:59

Last edit: 2019-10-14 12:36:06
nitish676: 2018-10-03 12:59:22

my submission id is:- 22434569 plz look at the solution and figure out what is wrong in it.

nazirzhumakhan: 2018-09-29 11:55:34

in test case 15 n = 0

nitish676: 2018-01-26 18:51:49

can you plz check solution id 21058493 whats wrong in it.

recurze: 2018-01-05 14:51:54

It is not explicitly mentioned that the coin values will be sorted. Sort if you need to.

Mallesh K: 2017-11-06 12:36:37

how to check which test case has failed?

Re: Well, unfortunately the user of the solver cannot check it though :/ (a.k.a. only problem creator can see it). Yours WA in TC 1 and then the other one TLE at test 4(maybe this helps XD)

Last edit: 2017-12-05 10:41:14
arsrivish2: 2017-10-08 10:55:06

Any help,or editorial for the above problem

Re: Well, for now, just read the problem carefully, I will make the editorial for tutorial problems that I've created soon :)

Last edit: 2017-12-05 10:42:47
badal: 2017-08-31 03:51:43

I am not getting the question..

hanstan: 2017-07-12 12:23:53

Re: To all ppl who think they were facing problems in the 15th test case, actually most of your source codes had failed from the first test case. FYI, SPOJ just simply runs your program from the first to the last test case and gives the verdict later. Check your algorithm and output format.

Last edit: 2017-07-12 12:31:27

Added by:hanstan
Date:2016-06-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY