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 a_i, a_i+1 where a_i is the order of i^th customer.

1 ≤ a_i <= 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