[Easy] Find the element that appears once in sorted array

Given a sorted array of integers, every element appears twice except for one. Find that single one in linear time complexity and without using extra memory.

Input:

The first line of input consists number of the test cases. The description of T test cases is as follows:

The first line of each test case contains the size of the array, and the second line has the elements of the array.

Output:

In each separate line print the number that appears only once in the array.

Constraints:

1 ≤ T ≤ 70
1 ≤ N ≤ 100
0 ≤ A[i] ≤ 100000

Example:

Input:
1
11
1 1 2 2 3 3 4 50 50 65 65

Output:
4