题目描述

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

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

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

输入包含 $T$ 组数据，各组数据之间是独立的。

输入格式

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

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

输出格式

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

输出数据#1

0
9
32
2
-1
-1
-1

数据范围

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

测试点

• 测试点 $1 \sim 2$（共 $20$ 分）：保证记录段落中包含至少一次完整的传输。
• 测试点 $3 \sim 6$（共 $40$ 分）：保证所给的记录可以确定保留字。
• 测试点 $7 \sim 10$（共 $40$ 分）：无特殊限制。
• 备注： 样例的倒数第二组数据是一种非法的传递格式（不存在保留字），和题目描述中说的“一定连续且符合前述格式”矛盾。这里认为官方测试数据和题目描述一致。（即，认为样例有问题）