不幸的是，Rabbit-Man 现在确实学到了一些更高级的算术。为了理解它，我们定义序列 $F_n$（与斐波那契数列不完全相同）：

$F_1 = 1$, $F_2 = 2$, $F_n = F_{n-1} + F_{n-2}$ 对于 $n \geqslant 3$。

Rabbit-Man 将他之前所有的邪恶想法结合成了一个总体计划。在第 $i$ 天，他在编号为 $p(i)$ 的地点进行了一次恶意行为，定义如下：

$p(i) = a_1 \cdot F_1^i + a_2 \cdot F_2^i + \dots + a_k \cdot F_k^i$。

数字 $k$ 和整数系数 $a_1, \dots, a_k$ 是固定的。Captain Obvious 知道了 $k$，但不知道这些系数。给定 $p(1), p(2), \dots, p(k)$，请帮助他确定 $p(k+1)$。为了避免数字过大，所有计算均在模一个固定的素数 $M$ 下进行。你可以假设 $F_1, F_2, \dots, F_n$ 在模 $M$ 下是两两不同的。你还可以假设对于给定的输入，总是存在唯一的解。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述： 每个测试用例的第一行包含两个整数 $k$ 和 $M$，$1 \leqslant k \leqslant 4000$，$3 \leqslant M \leqslant 10^9$。 第二行包含 $k$ 个以空格分隔的整数，即 $p(1), p(2), \dots, p(k)$ 模 $M$ 的值。

输出格式

按输入中出现的顺序打印测试用例的答案。对于每个测试用例，打印一行，包含一个整数：$p(k+1)$ 模 $M$ 的值。

样例

输入 1

2
4 619
5 25 125 6
3 101
5 11 29

输出 1

30
83

说明 1

第一个序列简单地为 $5^i \pmod{619}$，因此下一个元素为 $5^5 \pmod{619} = 30$。第二个序列为 $2 \cdot 1^i + 3^i \pmod{101}$。