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

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

给定一个长度为 $n$ 的整数数组 $a$。在本题中，该数组满足一个额外约束：数组 $a$ 中至少有一个整数恰好出现一次。请找到最小的正整数 $k$，使得 $f^k(a)$ 有定义，且数组 $f^k(a)$ 满足以下至少一个条件，或者报告不存在这样的 $k$：

• 存在一个整数在 $a$ 中只出现一次，但在 $f^k(a)$ 中至少出现两次；
• 存在一个整数在 $a$ 中至少出现两次，但在 $f^k(a)$ 中只出现一次。

由于答案可能非常大，请将其对 $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$)。数组中至少有一个值恰好出现一次。

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

输出格式

对于每个测试用例，输出一行答案，即对 $10^9 + 7$ 取模后的结果；如果不存在这样的 $k$，则输出 -1。

样例

样例输入 1

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

样例输出 1

1
1
-1
3