Omar and Mohamed are brothers. Mohamed loves candy, he just learned how to sum or subtract 2 numbers and Omar want to test his brother. So Omar will give Mohamed N numbers, and ask him to find the maximum number after make some calculation on them. Mohamed will use summation and subtraction to find that number without changing number's positions, if Mohamed answer right Omar will give him candy. Example: Omar give Mohamed -3, 4, 10 and Mohamed found that if he use summation on that numbers would get the maximum number (-3 + 4 + 10 = 11).

Input

Input starts with an integer T (T ≤ 100), the number of test cases. Each of the next 2*T lines. First line will be an integer N (1 <= N <= 100), Next line will be N integers. Each of these N integers will be between -1000 and 1000 (inclusive).

Output

For each test case, output one line in the format “Case t: a”, where t is the case number and a is the maximum number. (quotes for clarity).

Example

Input:
2
5
4 2 -6 0 5
3
-3 4 10

Output:
Case 1: 17
Case 2: 11