#1223. zxh的一气通贯

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: q3540555

题目描述

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

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

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

你可以从这 张牌构成的序列中选择一个长度为 的子序列 . 若存在一个正整数公比 , 使得 都有 , 则你成功构造 -一气通贯, 价值是 .

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

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

输入格式

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

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

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

第二行输入 个整数 , 表示起始手牌代表的序列.

输出格式

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

样例

样例输入

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

数据范围与提示

所有数据的 的总和不超过 .