Как всем известно, количество статей 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_n)$. Какова длина наибольшей подпоследовательности King в $B$?

Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов без изменения порядка оставшихся элементов.

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