无额外样例

问题描述

学完斐波那契数列后，小明同学也想构造一种数列。恰好他也刚学完素数，于是他通过以下方式开始构造：

首先，任意选择一个素数 p，令 A[1]=A[2]=p；而当 i ≥ 3 时，令 A[i]=A[i-1]·A[i-2]

例如，当选择 p=7 时，可以构造出如下数列：

7, 7, 49, 343, 16807, 5764801, ……

小明想知道，该数列的第 n 项的值，即 A[n] 是多少？你能告诉他吗？

类似的问题有 T 个。请你依次输出每个问题的答案。答案可能很大，你只需要输出 A[n] mod m 的值即可。

输入

第一行：两个整数 T, p;

接下来 T 行，每行两个整数 n，m。

输出

共 T 行，每行一个整数，表示对应的答案。

输入样例1

3 7
1 2
3 3
123456789 5

输出样例1

1
1
4

输入样例2

3 1000000007 
1 5
2 6
1234567890 876543210

输出样例2

2
5
261133381

数据范围

100% 的数据：$0 < T ≤ 5000, 0 < p, n < 2^{31}, 0 < m < p$。