Password

Rivest 是密码学专家。近日，他正在研究一个数列 $E=\{E_1,E_2,\ldots,E_n\}$，其中 $E_1=E_2=p$，$p$ 为一个质数；当 $2<i\le n$ 时，有：

$$E_i=E_{i-2}\times E_{i-1}。$$

例如，$p=2$ 时，数列为 $\{2,2,4,8,32,256,8192,\ldots\}$。

在此基础上，Rivest 又设计了一种加密算法。该算法通过密钥 $q$（$q<p$）将一个正整数 $n$ 加密为另一个正整数 $d$，计算公式为：

$$d=E_n\bmod q。$$

现在，Rivest 想对一组数据进行加密，但他对程序设计不感兴趣。请你帮助他设计一个数据加密程序。

输入格式

第一行输入两个整数 $m$ 和 $p$，其中 $m$ 表示数据个数，$p$ 用于生成数列 $E$。

接下来有 $m$ 行，每行包含两个整数 $n$ 和 $q$，其中 $n$ 为待加密数据，$q$ 为密钥。

输出格式

按输入顺序输出加密结果，每行输出一个加密后的数据。

样例输入

样例 $1$：

2 7
4 5
4 6

样例 $2$：

4 7
2 4
7 1
6 5
9 3

样例输出

样例 $1$：

3
1

样例 $2$：

3
0
1
1

数据范围

• $p$ 为质数，且 $0<p<2^{31}$；
• $0<n<2^{31}$；
• $0<q<p$；
• $0<m\le5000$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

2 7
4 5
4 6

输出

3
1

样例 2

输入

4 7
2 4
7 1
6 5
9 3

输出

3
0
1
1