该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

给定一个包含 $n$ 个元素的数组 $a$，请输出一个在数组中 至少出现 3 次 的值；如果不存在这样的值，则输出 $-1$。

原题允许输出任意一个满足条件的值。为适配只能固定输出的平台，本题规定： 若存在多个值满足至少出现 3 次，输出其中数值最小的那个。

输入格式

第一行输入整数 $t$（$1\le t\le 10^4$）表示测试用例数。

每个测试用例包含：

• 第一行一个整数 $n$（$1\le n\le 2\cdot 10^5$）表示数组长度；
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le n$）表示数组元素。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

输出格式

对每个测试用例输出一行一个整数：

• 若存在至少出现 3 次的值，输出 数值最小 的那个；
• 否则输出 $-1$。

样例

输入

7
1
1
3
2 2 2
7
2 2 3 3 4 2 2
8
1 4 3 4 3 2 4 1
9
1 1 1 2 2 2 3 3 3
5
1 5 2 4 3
4
4 4 4 4

输出

-1
2
2
4
1
-1
4