Jak wszyscy wiemy, liczba artykułów Panga rośnie wykładniczo. Dlatego jesteśmy ciekawi ciągu Kinga.

Dana jest liczba pierwsza $p$. Ciąg $(a_1, a_2, \dots, a_n)$ jest ciągiem Kinga wtedy i tylko wtedy, gdy istnieje liczba całkowita $1 \le q < p$ taka, że dla wszystkich liczb całkowitych $i \in [2, n]$, $q a_{i-1} \equiv a_i \pmod p$.

Mając dany ciąg $B = (b_1, \dots, b_n)$, jaka jest długość najdłuższego podciągu Kinga ciągu $B$?

Podciąg to ciąg, który można otrzymać z innego ciągu poprzez usunięcie pewnych elementów bez zmiany kolejności pozostałych elementów.

Pang jest ostatnio bardzo zajęty, więc jedyne, co chce wiedzieć, to czy odpowiedź jest większa lub równa $\frac{n}{2}$.

Jeśli długość najdłuższego ciągu Kinga jest mniejsza niż $\frac{n}{2}$, wypisz $-1$. W przeciwnym razie wypisz długość najdłuższego podciągu Kinga.

Wejście

Pierwsza linia zawiera liczbę całkowitą $T$ oznaczającą liczbę zestawów danych ($1 \le T \le 1000$).

Pierwsza linia w zestawie danych zawiera dwie liczby całkowite $n$ oraz $p$ ($2 \le n \le 200000$, $2 \le p \le 1000000007$, $p$ jest liczbą pierwszą). Suma $n$ we wszystkich zestawach danych nie przekracza $200000$.

Druga linia w zestawie danych zawiera ciąg $b_1, \dots, b_n$ ($1 \le b_i < p$).

Wyjście

Dla każdego zestawu danych wypisz jedną linię zawierającą odpowiedź, którą jest $-1$ lub długość najdłuższego podciągu Kinga.

Przykład

Wejście 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

Wyjście 1

5
-1
3
-1