{"raw_statement":[{"iden":"statement","content":"As we all know, the number of _Pang_'s papers follows exponential growth. Therefore, we are curious about _King_ sequence.\n\nYou are given a prime $p$. A sequence $(a_1, a_2, \\\\dots, a_n)$ is a _King_ sequence if and only if there is an integer $1 <= q < p$ such that for all integers $i in [ 2, n ]$, $q a_{i -1} equiv a_i pmod p$.\n\nGiven a sequence $B = (b_1, \\\\dots, b_m)$, what is the length of the longest _King_ subsequence of $B$? \n\nA subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.\n\n$P a n g$ 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)$. \n\nIf the length of the longest _King_ sequence is less than $frac(n, 2)$, output $-1$. Otherwise, output the length of the longest _King_ subsequence.\n\nThe first line contains an integer $T$ denoting the number of test cases ($1 <= T <= 1000$).\n\nThe first line in a test case contains two integers $n$ and $p$ ($2 <= n <= 200000$, $2 <= p <= 1000000007$, $p$ is a prime). The sum of $n$ over all test cases does not exceed $200000$.\n\nThe second line in a test case contains a sequence $b_1, \\\\dots, b_n$ ($1 <= b_i < p$).\n\nFor each test case, output one line containing the answer which is $-1$ or the length of the longest _King_ subsequence.\n\n"},{"iden":"input","content":"The first line contains an integer $T$ denoting the number of test cases ($1 <= T <= 1000$).The first line in a test case contains two integers $n$ and $p$ ($2 <= n <= 200000$, $2 <= p <= 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, \\\\dots, b_n$ ($1 <= b_i < p$)."},{"iden":"output","content":"For each test case, output one line containing the answer which is $-1$ or the length of the longest _King_ subsequence."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ p $ be a prime. A sequence $ (a_1, a_2, \\dots, a_n) $ is a *King sequence* if there exists an integer $ q \\in [1, p-1] $ such that for all $ i \\in [2, n] $,  \n$$\na_i \\equiv q \\cdot a_{i-1} \\pmod{p}.\n$$\n\nGiven a sequence $ B = (b_1, b_2, \\dots, b_n) $, let $ \\mathcal{K}(B) $ denote the set of all King subsequences of $ B $.\n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. For each test case:  \n   - $ 2 \\le n \\le 200000 $, $ 2 \\le p \\le 1000000007 $, $ p $ prime  \n   - $ 1 \\le b_i < p $ for all $ i \\in \\{1, \\dots, n\\} $  \n   - Total sum of $ n $ across test cases $ \\le 200000 $\n\n**Objective**  \nFor each test case, compute:  \n$$\nL = \\max \\{ |S| \\mid S \\in \\mathcal{K}(B) \\}\n$$  \nIf $ L < \\left\\lceil \\frac{n}{2} \\right\\rceil $, output $ -1 $.  \nOtherwise, output $ L $.","simple_statement":"Given a sequence and a prime p, find the longest subsequence where each element (after the first) is q times the previous one modulo p, for some q between 1 and p-1. If this longest length is at least n/2, output it; otherwise, output -1.","has_page_source":false}