Description

Sean 和 Patrick 是一对兄弟，他们刚刚从父母那里得到了一袋美味的糖果。每颗糖果都有一个正整数的价值，兄弟俩想要把糖果分成两份。首先，Sean 会把糖果分成两堆，并选择其中一堆送给 Patrick。然后 Patrick 会尝试计算每堆的价值，其中一堆的价值是该堆所有糖果价值的总和；如果他发现两堆的价值不相等，他就会开始哭泣。

不幸的是，Patrick 还很小，不太会加法。他“几乎”会用二进制加法；但每当他遇到两个 $1$ 相加时，总是忘记向下一位进位。例如，如果他想把 $12$（二进制 $1100$）和 $5$（二进制 $101$）相加，他会正确地加上最右边的两位，但在第三位时会忘记进位：

  1100
+ 0101
------
  1001

所以在加完最后一位且没有从第三位进位后，最终结果是 $9$（二进制 $1001$）。以下是 Patrick 算数能力的其他例子：

5 + 4 = 1
7 + 9 = 14
50 + 10 = 56

Sean 很擅长加法，他想在不让弟弟哭泣的前提下，尽可能多地拿到糖果。如果可能的话，他会把糖果分成两堆且都不为空，使得 Patrick 认为两堆的价值相等。给定糖果袋中所有糖果的价值，请你判断是否有可能做到；如果可能，请计算 Sean 能拿到的最大糖果价值。

Input Format

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来的 $T$ 个测试用例，每个测试用例包含两行。第一行是一个整数 $N$，表示糖果的数量。第二行包含 $N$ 个用空格分隔的整数 $C_i$，表示每颗糖果的价值。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始）。如果 Sean 无法让 Patrick 不哭泣，则 $y$ 为 "NO"。否则，$y$ 为 Sean 能拿到的糖果堆的最大价值。

2
5
1 2 3 4 5
3
3 5 6

Case #1: NO
Case #2: 11

Hint

数据范围

• $1 \leq T \leq 100$。
• $1 \leq C_i \leq 10^6$。

小数据范围（10 分，测试点 1 - 可见）

• $2 \leq N \leq 15$。
• 时间限制：3 秒。

大数据范围（15 分，测试点 2 - 隐藏）

• $2 \leq N \leq 1000$。
• 时间限制：6 秒。

由 ChatGPT 4.1 翻译