#1223. zxh的一气通贯

ツモ！ダブル立直 一発 門前清自摸和 一気通貫 清一色 赤ドラ！13番！数え役満！48000点！

随着一阵报菜名, 整盘麻将变得索然无味. 上述的报菜名中有一个2番役叫做一气通贯 (一気通貫), 一气通贯的定义是有同色的 123-456-789 三个顺子, Sheauhaw 发现一气通贯的组成牌刚好构成了公差为 $1$ 的一个等差数列, 于是就想到构造一种新役种, 叫做几何一气通贯.

Sheauhaw 先告诉你了一个幸运素数 $p$, 用于构造域结构, 在这个域下构造的几何一气通贯叫做 $p$-一气通贯. 于是你的手牌中有 $n$ 张按顺序排列的牌 $a_1,a_2,\cdots,a_n$ , 每种数字的牌可能会超过四张, 且牌面数值小于 $p$.

你可以从这 $n$ 张牌构成的序列中选择一个长度为 $m$ 的子序列 $b_1,b_2,\cdots,b_m$. 若存在一个正整数公比 $q$, 使得 $\forall i\in[1,m)$ 都有 $qb_i\equiv b_{i+1}\pmod p$, 则你成功构造 $p$-一气通贯, 价值是 $m$.

Sheauhaw 不喜欢短的东西, 所以要求构造 $p$-一气通贯的价值不小于 $n/2$.

你的任务是, 告诉 Sheauhaw 能构造的 $p$-一气通贯的最大价值. 如果不能构造价值不小于 $n/2$ 的 $p$-一气通贯, 则输出 $-1$.

第一行输入一个整数 $T$, 表示数据组数.

对于每组输入数据, 输入两行:

第一行输入两个整数 $n,p$, 表示手牌数量和域结构特征.

第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$, 表示起始手牌代表的序列.

对于每组输入数据, 输出一行, 一行输出一个整数 $A$, 表示能构造的 $p$-一气通贯的最大价值. 如果没有答案, 输出 $-1$.

样例输入

4
6 1000000007
1 1 2 4 8 16
6 1000000007
2 3 5 7 11 13
5 1000000007
2 4 5 6 8
5 1000000007
2 4 5 6 7

样例输出

5
-1
3
-1

$1\le T\le1000$

$1\le n\le200000$

$2\le p\le1000000007$

$1\le a_1,a_2,\cdots,a_n<p$

所有数据的 $n$ 的总和不超过 $200000$.