眾所周知，Pang 的論文數量呈指數級增長。因此，我們對 King 序列感到好奇。

給定一個質數 $p$。一個序列 $(a_1, a_2, \dots, a_n)$ 被稱為 King 序列，若且唯若存在一個整數 $1 \le q < p$，使得對於所有整數 $i \in [2, n]$，滿足 $q a_{i-1} \equiv a_i \pmod p$。

給定一個序列 $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