G. Pretty Prime Collection
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a deck of $$$n$$$ cards, each labeled with a number $$$a_i$$$. The game begins with an empty hand and an initial total score of zero.

On the $$$i$$$-th turn, you must pick up the $$$i$$$-th card with value $$$a_i$$$, then optionally discard some cards from your hand, ensuring that after this step, the bitwise XOR$$$^{[8]}$$$ of any two remaining cards in hand is a prime number$$$^{[11]}$$$. The score for this turn is the sum of the values of all cards in your hand, which is then added to the total score.

Determine the maximum possible total score after completing all $$$n$$$ turns.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 150$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \lt 2^{20}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$150$$$.

Output

For each test case, output one line containing a single integer — the maximum score you can get.

Example
Input
3
5
1 2 3 4 5
9
9 9 8 2 4 4 3 5 3
2
323468 765165
Output
24 
103 
1412101
Note

Cards picked during their respective turns are underlined, while discarded cards are crossed out.

In the first test case, you can process the initial empty hand $$$\{\}$$$ and total score $$$0$$$ as follows:

  • after completing the first turn: $$$\{\underline{1}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1\}$$$ and a total score of $$$0 + 1 = 1$$$;
  • after completing the second turn: $$$\{1, \underline{2}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 2\}$$$ and a total score of $$$1 + 3 = 4$$$;
  • after completing the third turn: $$$\{1, \not{2}, \underline{3}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 3\}$$$ and a total score of $$$4 + 4 = 8$$$. Note that cards with values $$$2$$$ and $$$3$$$ cannot be held in hand simultaneously since $$$2 \oplus 3 = 1$$$, which isn't a prime number. To resolve this, we can discard the card with value $$$2$$$;
  • after completing the fourth turn: $$$\{1, 3, \underline{4}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 3, 4\}$$$ and a total score of $$$8 + 8 = 16$$$;
  • after completing the fifth turn: $$$\{1, 3, 4, \not{\underline{5}}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 3, 4\}$$$ and a total score of $$$16 + 8 = 24$$$.