时间限制：1秒　　内存限制：256M

---

【题目描述】

　　求 \(A^X\) 所有约数和，结果 \(mod\ B\)（其中 \(B\) 是一个质数）。

【输入格式】

　　第一行为整数 \(T\) 和 \(A\)。
　　接下来的 \(T\) 行，每行包含两个整数：\(X\ B\)，其中 \(B\) 是一个质数。

【输出格式】

　　输出 \(T\) 行，对于每个输入的 \(X\) 和 \(B\)，输出 \(A^X\) 的约数和 \(mod\ B\) 的结果。

【输入输出样例】

　Input

2 2004
1 29
10000 29

　Output

6
10

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤A,B,X≤10^9\)，最多100000组数据。

【来源】

　　Mr.he