Migrated from Lutece 565 KKX Sequence

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

KKX likes to play with sequences and find interesting things. For an integer sequence $A_1, A_2, \cdots , A_N$, he subtracts every adjacent two elements to get another sequence of length $N-1$, $B_1, B_2, \cdots, B_{N-1}$, where $B_i = A_i - A_{i+1}$, $i = 1, 2, \cdots, N-1$. Keep on this method until only one element left. Obviously, for a sequence this number is unique.

KKX wants to know if he can rearrange the elements in the initial sequence $A$ in any order, what is maximal number left using the method above?

Please use $64$-bit integers(long long in C/C++) to do calculation in this problem. And use the %lld specificator to read or write $64$-bit integers in C/C++.

Input

There will be multiple test cases. The first line of the input is an integer $T$ ($T \leq 100$) indicating the number of test cases.

For each test case an integer $N$ ($1 \leq N \leq 50$) comes first indicating the number of elements in the initial sequence $A$. The next line contains $N$ integers with absolute value within $1000$.

Output

Print Case #k: x in a single line for each test case, in which $k$ represents the case number which starts from $1$, and $x$ is the maximal number left.

Samples

2
3
1 1 -1
5
2 1 5 -4 2

Case #1: 4
Case #2: 46

Resources

10th UESTC Programming Contest Preliminary