{"problem":{"name":"H. King","description":{"content":"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, \\\\dots, a_n)$ is a _King_ ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10247H"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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$).\n\n## Output\n\nFor each test case, output one line containing the answer which is $-1$ or the length of the longest _King_ subsequence.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10247H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}