描述

_L的室友HZ喜欢在川大贴吧上发帖,据传说,HZ在川大贴吧上发的贴子数已经超过了该贴吧贴子总数的一半,被江湖人封为川大贴吧水王,你能帮_L迅速找出这位川大贴吧水王HZ的ID吗?

已知川大贴吧贴子总数为n,给出n个贴子作者的ID,求HZ的ID。

Input

输入文件包含多组测试数据。第一行为测试的数据组数T(T<=40)。
接下有T组数据,第一行输入贴子总数n(1<=n<=10000000),接下来的一行有n个正整数,分别为每位贴子作者的ID号(该ID号为不超过10^9的正整数)

Output

输出T行,每行为该组测试数据的川大贴吧水王HZ的ID。

Example Input

2
3
1 2 2
5
1 2 3 3 3

Example Output

2
3

Author

_L