Marks :15

: 5 | : 1

You are given an array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. It is also guaranteed that the duplicate occurrences occur consecutively.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Input

The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.

The first line of each testcase contains an integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — the size of array $$$A$$$.

The second line of each testcase contains $$$n$$$ space separated integers $$$a_1, a_2,... a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — the elements of array $$$A$$$.

It is guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and every element appears exactly twice consecutively, except for one element which appears exactly once.

Output

For each test case, print the element that appears exactly once in a single line.

Example

Input

291 1 2 3 3 4 4 8 873 3 7 7 10 11 11

Output

2 10

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Successful

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

But to **Run** or **Submit** the Problem, you need to Log In.

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Do let us know your issue.