NAJSO - Shopkeeper Order

no tags 

Mr. Rahman is our village shopkeeper. He only sells oil. Every day he has n client orders, and he delivers the orders the next day. His client keep their oil drum in his shop. He has different size of oil drum to fill the clients' drums. Every day he collect his orders and select a drum he can use to fulfil all his clients' orders without any fraction. Suppose today he got 5 clients’ orders: 10 liter, 30 liter, 40 liter, 75 liter and 25 liter. Now he can choose a 5 liter drum to fill all the customer drums.

Now help Mr. Rahman to choose the maximum size of oil drum which can fulfil all the client drum.

Input

The first line contains the number of test cases T≤100. Each of the next lines contains an integer N<=10^5. Next line give N integer ai, ai+1 where ai is the order of ith customer.

1 ≤ ai <= 10^9

Output

Output T lines one for each test case print Case number and the maximum size of Mr. Rahman's oil drum.

Example

Input:
2
5
10 30 40 75 25
4
4 10 40 12

Output:
Case 1: 5
Case 2: 2

hide comments
Jacob Plachta: 2014-10-26 04:41:34

Moved to Tutorial.

Najmuzzaman: 2014-10-26 02:57:48

@:P Now it Submittable.

:P: 2014-10-26 02:55:58

y is it not possible to submit the solution?? :(


Added by:Najmuzzaman
Date:2014-10-25
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64