众所周知，Pang 的论文数量呈指数级增长。因此，我们对 King 序列产生了兴趣。

给定一个素数 $p$。当且仅当存在一个整数 $1 \le q < p$，使得对于所有整数 $i \in [2, n]$，都有 $q a_{i-1} \equiv a_i \pmod p$ 时，序列 $(a_1, a_2, \dots, a_n)$ 被称为 King 序列。

给定一个序列 $B = (b_1, \dots, b_m)$，求 $B$ 的最长 King 子序列的长度是多少？

子序列是指可以通过删除原序列中某些元素，且不改变剩余元素顺序而得到的序列。

Pang 最近非常忙，所以他只想知道答案是否大于或等于 $\frac{n}{2}$。

如果最长 King 子序列的长度小于 $\frac{n}{2}$，则输出 $-1$。否则，输出最长 King 子序列的长度。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 1000$)。

每个测试用例的第一行包含两个整数 $n$ 和 $p$ ($2 \le n \le 200000, 2 \le p \le 1000000007, p$ 为素数)。所有测试用例中 $n$ 的总和不超过 $200000$。

每个测试用例的第二行包含一个序列 $b_1, \dots, b_n$ ($1 \le b_i < p$)。

输出格式

对于每个测试用例，输出一行，包含答案（$-1$ 或最长 King 子序列的长度）。

样例

输入格式 1

4
6 1000000007
1 1 2 4 8 16
6 1000000007
597337906 816043578 617563954 668607211 89163513 464203601
5 1000000007
2 4 5 6 8
5 1000000007
2 4 5 6 7

输出格式 1

5
-1
3
-1