시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 256 MB | 7 | 5 | 5 | 71.429% |
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