誰もが知る通り、Pangの論文数は指数関数的に増加している。そのため、我々は King sequence に興味を持っている。

素数 $p$ が与えられる。数列 $(a_1, a_2, \dots, a_n)$ が King sequence であるとは、ある整数 $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 部分列の長さを出力せよ。

入力

1行目にはテストケースの数 $T$ が含まれる ($1 \le T \le 1000$)。

各テストケースの1行目には、2つの整数 $n$ と $p$ が含まれる ($2 \le n \le 200000$, $2 \le p \le 1000000007$, $p$ は素数)。すべてのテストケースにおける $n$ の総和は $200000$ を超えない。

各テストケースの2行目には、数列 $b_1, \dots, b_n$ が含まれる ($1 \le b_i < p$)。

出力

各テストケースについて、答えである $-1$ または最長の King 部分列の長さを1行で出力せよ。

入出力例

入力 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