Candy Splitting

Sean and Patrick are brothers who just got a bag of candy from their parents. Every 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 picks one of them 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 pieces in it. If he decides the two piles do not have the same value, he starts crying.

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

  1100
+ 0101
------
  1001

After adding the last bit without the carry from the third bit, the result is 9 (1001 in binary). Patrick's arithmetic works like this.

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

Sean adds well, and he wants to keep as much value as he can without making his brother cry. If it is possible, he splits the bag into two non-empty piles such that Patrick thinks both have the same value. Given the values of all the pieces 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 a single integer $N$, the number of pieces of candy in the bag. The next line contains the $N$ values $C_i$, separated by single spaces.

Limits

• $1 \le T \le 100$
• $2 \le N \le 15$
• $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 has no way to keep Patrick from crying, y is the word NO. Otherwise, y is the value of the pile Sean keeps.