Given a linked list, find the middle element and print its value.

If the list has even number of elements, print the first of the two middle elements.

Examples:

List: 1→8→3

Middle element: 8

List: 1→3→8→5

Middle element: 3

Testing

Input Format

The first line contains ‘T’ denoting the number of independent test cases.

For each test case the input has two lines:

• An integer ‘n’ denoting the length of the linked list.
• n space-separated integers denoting elements of the linked list.

Output Format

For each test case, a line containing an integer denoting the middle element of the linked list.

Sample Input

2
4
3 4 5 6
1
3

Expected Output

4
3

Constraints

1 <= T <= 100
1 <= n <= 103
1 <= element <= 105