Candy Splitting (Large)

Sean and Patrick are brothers who just got a bag of candy from their parents. Each piece of candy has a positive integer value, and the brothers want to divide the candy between them. Sean first splits the candy into two piles and chooses one pile to give to Patrick. Patrick then computes the value of each pile, where the value of a pile is the sum of the values of the candy in it. If he decides the two piles do not have equal value, he starts crying.

Patrick is very young and does not know how to add properly. He almost knows how to add in binary, but whenever he adds two 1s he forgets to carry the remainder to the next bit. For example, when he adds 12 (1100 in binary) and 5 (101 in binary), he adds the two rightmost bits correctly, but in the third bit he forgets to carry the remainder.

  1100
+ 0101
------
  1001

After the last bit is added without that carry, the result is 9 (1001 in binary). Here are more examples of Patrick's arithmetic.

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

Sean is very good at adding, and he wants to keep as much value as he can without making his little brother cry. If it is possible, he splits the bag into two non-empty piles such that Patrick thinks both piles have the same value. Given the values of all the candy in the bag, decide whether such a split exists, and if it does, find the maximum possible value of Sean's pile.

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case is described in two lines. The first line contains the number of candies in the bag, $N$. The next line contains the $N$ values $C_i$, separated by single spaces.

Limits

• $1 \le T \le 100$
• $2 \le N \le 1000$
• $1 \le C_i \le 10^6$

For each test case, output one line containing "Case #x: y", where $x$ is the test case number starting from 1. If Sean cannot keep Patrick from crying, $y$ is the word NO. Otherwise $y$ is the value of the pile Sean keeps.