题目描述

对于一个集合 $S$，我们进行 $n$ 次操作，每次加入或者删除一个正整数，求每次操作后集合中所有数字的最大公约数。

输入格式

第一行一个整数 $T(1\leq T \leq 10)$代表数据组数。

每组数据第一行一个数 $n(1\leq n \leq 2*10^5)$，代表操作次数。

下面每行一个数字 $a_i(1\leq a_i \leq 10^9)$ 若 $a_i$ 不在集合中，则将 $a_i$ 加入集合，否则将其删除。

输出格式

每组数据 $n$ 行，每行一个数字表示当前集合所有数字的最大公约数，如果的前集合为空集则输出 $-1$。

样例

输入样例

1
6
12
6
4
12
4
6

输出样例

12
6
2
2
6
-1