Problem Description

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

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

$$f_i = f_{i-1} + f_{i-2} (i \ge 2)\\ f_0 = 0, f_1 = 1$$

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

定义矩阵含义为 $\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}$ ，即：

$$\begin{bmatrix}f_{i+1} & f_{i} & f_{i-1}\end{bmatrix} \Leftarrow \begin{bmatrix}f_i & f_{i-1}& f_{i-2}\end{bmatrix} \times \begin{bmatrix}1 &1& 0\\ 1 &0& 1\\ 0 &0&0 \end{bmatrix}$$

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

$$\begin{bmatrix}f_{i+1} & f_{i}\end{bmatrix} \Leftarrow \begin{bmatrix}f_i & f_{i-1}\end{bmatrix} \times \begin{bmatrix}1 &1\\ 1 &0\end{bmatrix}$$

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

现在给定 $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$