E. Minimize Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of $$$n$$$ integers, find the minimum sum of the array after removing two elements of $$$a$$$ and appending their bitwise XOR to the array.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2, \ldots ,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

—

Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1 - 5$$$ will satisfy $$$t \le 10$$$, $$$n \le 1000$$$.

The remaining tests do not satisfy any additional constraints.

Output

For each test case, output a single integer — the minimum achievable sum.

Example
Input
2
5
5 1 1 3 2
3
1 4 9
Output
8
12
Note

In the first test case of the sample test, it is optimal to choose the elements $$$2$$$ and $$$3$$$, deleting them and appending $$$1$$$ to the array. This produces a new sum of $$$8$$$.

In the second test case of the sample test, it is optimal to choose the elements $$$1$$$ and $$$9$$$, deleting them and appending $$$8$$$ to the array. This produces a new sum of $$$12$$$.

—

Problem Idea: xug

Problem Preparation: xug

Occurrences: Novice E