Description

  蛤先生是一位著名的科学家,不久前他得到了一种名叫“熵破坏者”的药剂。这种药被保存在 NN 个瓶子中,其中第 ith(1iN)i^{th}(1\leq i\leq N) 个瓶子盛有 ViV_i 升药剂。为了让“熵破坏者”发挥魔力,他必须把所有保存在瓶子中的药剂混合在一起。
  由于混合药剂是一件危险的工作,蛤先生取出了他珍藏已久的大容器,并打算把药剂以整瓶为单位,全部倒进大容器中。大容器的容量可以看作无穷大。若大容器中已有 pp 升药剂,则再倒入 qq 升药剂后,大容器中剩余药剂的体积是 pq|p-q|(神奇的混合方法!)。
  最初,大容器是空的,蛤先生可以以任意一种顺序把每瓶药剂倒入大容器。最终,若大容器中还剩余 RR 升药剂,则蛤先生就可以使用一次魔法,把自己的生命周期续 RR 秒。请帮蛤先生求出可能混合成的最大的 RR,即蛤先生这次最多可以续几秒。

Input

  输入包含多组数据,在数据开头有一个整数 T(T5)T(T\leq 5),表示组数。对于每组数据:
  第一行一个整数 NN,第二行 NN 个整数 ViV_i

Output

  对于每组数据,先输出 "Case #k: ",其中k是该组数据的编号,从1开始,然后紧接着输出最大的 RR

Sample Input
3
4
1 2 2 9
1
-1
10
1 3 0 0 0 1 2 7 3 7
Sample Output
Case #1: 8
Case #2: 1
Case #3: 6
Hint

数据范围与约定
  对于 20%20\% 的数据,1N101\leq N \leq 10
  对于 60%60\% 的数据,1N501\leq N \leq 50
  对于 100100% 的数据,1N2001\leq N \leq 200