You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

矩阵快速幂当然是签到题啦！

大家都知道斐波拉契数列的定义如下：

在大一时，大家都学过了矩阵，现在凤爪老师决定检验一下大家学习情况。凤爪老师写出了如下式子：

定义矩阵含义为 $\begin{bmatrix}f_i& f_{i-1} & f_{i-2}\end{bmatrix}$ 。

因为 $f_i = f_{i-1}+f_{i-2}$ ，所以 $f_{i+1} = f_i + f_{i-1}$ ，即：

当然最后一维是没必要的，可以写为：

这样就成功的更新了斐波那契数列，加上快速幂就可以达到快速求取的目的。当然，凤爪老师不想自己实现，所以他让你来负责完成。

现在给定 $q$ 次询问，每次给出一个自然数 $n$ ，请你求出斐波那契数列的第 $n$ 项的值，由于这个值可能很大，你需要对给出的 $k$ 取模。

Input Format

第一行包括一个正整数 $T$，表示测试的组数。

对于每组测试数据：

第一行输入两个整数 $q$ 和 $k$，分别表示询问次数和模数。

接下来 $q$ 行，每行输入一个自然数 $n$，表示一次询问。

Output Format

对于每次询问，输出一行一个整数，表示 $f_n \mod k$ 的值。

Sample

样例输入 1

1
3 1000000007
0
1
10

样例输出 1

0
1
55

Hint

• $1 \leqslant n \leqslant 10^{18}$
• $1 \leqslant k \leqslant 10^9 + 7$， 注意 $k$ 等于 $1$ 的情况。
• $1 \leqslant \Sigma q \leqslant 4 \times 10^4$