406653: GYM102471 H King

As we all know, the number of Pang's papers follows exponential growth. Therefore, we are curious about King sequence.

You are given a prime $$$p$$$. A sequence $$$(a_1,a_2,\ldots,a_n)$$$ is a King sequence if and only if there is an integer $$$1\leq q < p$$$ such that for all integers $$$i\in [2,n]$$$, $$$q a_{i-1} \equiv a_i \pmod p$$$.

Given a sequence $$$B=(b_1,\ldots,b_m)$$$, what is the length of the longest King subsequence of $$$B$$$?

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

$$$Pang$$$ is super busy recently, so the only thing he wants to know is whether the answer is greater than or equal to $$$\frac{n}{2}$$$.

If the length of the longest King sequence is less than $$$\frac{n}{2}$$$, output $$$-1$$$. Otherwise, output the length of the longest King subsequence.

The first line contains an integer $$$T$$$ denoting the number of test cases ($$$1\le T\le 1000$$$).

The first line in a test case contains two integers $$$n$$$ and $$$p$$$ ($$$2\le n \le 200000$$$, $$$2\le p \le 1000000007$$$, $$$p$$$ is a prime). The sum of $$$n$$$ over all test cases does not exceed $$$200000$$$.

The second line in a test case contains a sequence $$$b_1,\ldots, b_n$$$ ($$$1\le b_i< p$$$).

For each test case, output one line containing the answer which is $$$-1$$$ or the length of the longest King subsequence.

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

5
-1
3
-1