Majority Element Finder

Given an array of integers for each test case, there is a majority element that appears more than \( \lfloor n/2 \rfloor \) times (where \( n \) is the size of the array). Your task is to find and output the majority element for each test case.

The input starts with an integer \( T \) indicating the number of test cases. For each test case, the first line contains an integer \( n \) which is the number of elements in the array. The next line contains \( n \) space-separated integers representing the array elements. It is guaranteed that a majority element always exists in each test case.

The output should contain the majority element for each test case on a new line.

inputFormat

The input is read from standard input (stdin) with the following format:

T
n_1
a[1] a[2] ... a[n_1]
n_2
a[1] a[2] ... a[n_2]
...
n_T
a[1] a[2] ... a[n_T]

Where:

• T is the number of test cases.
• For each test case, n is the number of integers in the array.
• The next line contains n space-separated integers.

outputFormat

For each test case, print the majority element on a separate line to standard output (stdout).

## sample

1
5
3 3 4 2 3

3

</p>