对于一个整数数组 $b$，定义 $f(b)$ 为与 $b$ 长度相同、字典序大于 $b$ 且字典序最小的数组，且该数组与 $b$ 包含的元素集合相同。如果不存在这样的数组，则 $f(b)$ 未定义。例如，$f([3, 2, 3, 2, 6, 6]) = [3, 2, 3, 3, 2, 6]$。在本题中，“数组的元素集合”指数组元素构成的无序集合，其中每个元素无论在数组中出现多少次，都只被考虑一次。数组 $[3, 2, 3, 2, 6, 6]$ 和 $[3, 2, 3, 3, 2, 6]$ 具有相同的元素集合 $\{2, 3, 6\}$，尽管某些值在第一个数组和第二个数组中出现的次数不同。

令 $f^k(b)$ 表示函数 $f$ 对 $b$ 应用 $k$ 次的结果；此处我们认为 $f(\text{undefined})$ 同样为未定义。例如，$f^2([3, 2, 3, 2, 6, 6]) = f([3, 2, 3, 3, 2, 6]) = [3, 2, 3, 3, 3, 6]$。

给定一个长度为 $n$ 的整数数组 $a$。在本题中，该数组满足一个附加约束：数组 $a$ 中的每个值至少出现两次。请找到最小的正整数 $k$，使得 $f^k(a)$ 有定义，且数组 $f^k(a)$ 中存在某个值恰好出现一次；如果不存在这样的 $k$，请报告无解。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

输入包含一个或多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

每个测试用例由两行给出。第一行包含一个整数 $n$ ($2 \le n \le 10^5$)。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)。数组 $a$ 中的每个值至少出现两次。

所有测试用例的 $n$ 之和不超过 $6 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含答案对 $10^9 + 7$ 取模的结果，如果无解则输出 -1。

样例

输入 1

3
6
3 2 3 2 6 6
3
6 6 6
8
1 1 4 3 3 4 1 1

输出 1

1
-1
9