406653: GYM102471 H King

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Kingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$$$).

Output

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

ExampleInput
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
Output
5
-1
3
-1

加入题单

上一题 下一题 算法标签: