题目描述

空间站的舱室越来越多，有些太空舱在维护期间是不能进入的，常规的通讯手段也会因断电而无法使用。因此各舱之间有一台-次可以传输一 个非负整数的机器。现在希望利用它传输非空的整数数列，为此定义一种通讯协议，用于各舱之间的应急通讯。

在传输前，双方事先约定一个整数作为保留字。传输时，连续三次出现保留字表示传输开始或结束，正文中每两个数字之间插入一个保留字。如数列1 2 3 4 5，约定保留字为0，则一次完整的传输为0 0 0 1 0 2 0 3 0 4 0 5 0 0 0。已知传输的正文不含保留字。

现在给出n个整数，它们是某台机器发送的数据的一段记录(可能不完整，只是其中片段，但一定连续且符合前述格式)，试确定保留字或指出这段记录无法确定保留字。请注意，输入的记录段落中既可能包含不止一次完整的传输，也可能一次完整的传输中间的片段。

输入格式

输入的第1行包含1个整数T，表示数据组数。

接下来2T行，每2行描述组数据。其中前一行是1个整数n，表示下一行记录片段的长度；后一行是n个整数的值，表示发送的数据的一段记录。

输出格式

输出T行，每行1个整数，表示对应该组数据的保留字。如果根据所给的记录片段无法确定保留字，输出-1。

输入样例

7
15
0 0 0 1 0 2 0 3 0 4 0 5 0 0 0
4
9 9 9 1
7
32 80 32 8 32 0 32
8
3 2 1 2 3 2 5 2 
2
7 9
8
3 5 3 7 3 10 5 9
8
9 5 9 5 9 5 9 5

输出样例

0
9
32
2
-1
-1
-1

数据范围与约定

对于全部数据，有1≤T≤10，1≤n≤10000。输入数据中所有数均为不超过10000的非负整数。

测试点1~2 (共20分) : 保证记录段落中包含至少一次完整的传输。

试点3~6 (共40分) : 保证所给的记录可以确定保留字。

测试点7~10 (共40分) : 无特殊限制。