题目描述

众所周知，$\textit{Pang}$ 的论文数量呈指数增长。因此，我们对 $\textit{King}$ 序列产生了好奇。

给定一个质数 $p$。当且仅当存在一个整数 $1\leq q < p$，使得对于所有整数 $i\in [2,n]$，都有 $q a_{i-1} \equiv a_i \pmod p$，则序列 $(a_1,a_2,\ldots,a_n)$ 被称为 $\textit{King}$ 序列。

给定一个序列 $B=(b_1,\ldots,b_m)$，请问 $B$ 的最长 $\textit{King}$ 子序列的长度是多少？

子序列指的是从原序列中删除若干元素（可以为零），且不改变剩余元素的相对顺序后得到的序列。

$Pang$ 最近非常忙，所以他只关心答案是否大于等于 $\frac{n}{2}$。

如果最长 $\textit{King}$ 序列的长度小于 $\frac{n}{2}$，输出 $-1$。否则，输出最长 $\textit{King}$ 子序列的长度。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量（$1\le T\le 1000$）。

每个测试用例的第一行包含两个整数 $n$ 和 $p$（$2\le n \le 200000$，$2\le p \le 1000000007$，$p$ 为质数）。所有测试用例中 $n$ 的总和不超过 $200000$。

每个测试用例的第二行包含一个长度为 $n$ 的序列 $b_1,\ldots, b_n$（$1\le b_i< p$）。

输出格式

对于每个测试用例，输出一行答案，若最长 $\textit{King}$ 子序列长度小于 $\frac{n}{2}$，则输出 $-1$，否则输出最长 $\textit{King}$ 子序列的长度。

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

提示

由 ChatGPT 4.1 翻译