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(AB); }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 different coins he can collect in a single withdrawal.
Input
The first line of input contains of an integer T (1 ≤ T ≤ 10^{2}) , the number of test cases. Each of the test cases starts with n (0 ≤ n ≤ 10^{4}), 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^{9}.
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
Output 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(6332=31) withdraw(31)>B(highest value coin that does not exceed A=16) coin is given to customer. Call withdraw(3116=15) withdraw(15)>B(highest value coin that does not exceed A=8) coin is given to customer. Call withdraw(158=7) withdraw(7)>B(highest value coin that does not exceed A=4) coin is given to customer. Call withdraw(74=3) withdraw(3)>B(highest value coin that does not exceed A=2) coin is given to customer. Call withdraw(32=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! 1,2,4,8,16, and 32. Hope this clarifies you 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
harshwardhan26:
20191014 12:34:59
Last edit: 20191014 12:36:06 

nitish676:
20181003 12:59:22
my submission id is: 22434569 plz look at the solution and figure out what is wrong in it.


nazirzhumakhan:
20180929 11:55:34
in test case 15 n = 0 

nitish676:
20180126 18:51:49
can you plz check solution id 21058493 whats wrong in it.


recurze:
20180105 14:51:54
It is not explicitly mentioned that the coin values will be sorted. Sort if you need to. 

Mallesh K:
20171106 12:36:37
how to check which test case has failed?


arsrivish2:
20171008 10:55:06
Any help,or editorial for the above problem


badal:
20170831 03:51:43
I am not getting the question..


hanstan:
20170712 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: 20170712 12:31:27 

shefali11:
20170705 23:12:37
test case 15?? :' 
Added by:  hanstan 
Date:  20160622 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 