LK的项链二
LK的男朋友又送给LK一盒有珠子(珠子有很多很多)，但是这一次一共有n种颜色，并且每一种颜色的珠子个数都大于n个，现在LK想用这一盒珠子穿出一条项链，项链上的珠子个数也为n（1<=n<2^31）,现在请你计算一下可以穿出的项链的种数。通过旋转可以达到一种状态的被认为是相同的项链，翻转视为不同。
Input
第一行有一个整数t<=3500
随后t行每行有两个整数n、p，n表示颜色的种类和项链上珠子的个数。p表示求出结果后对p取余数。
随后t行每行有两个整数n、p，n表示颜色的种类和项链上珠子的个数。p表示求出结果后对p取余数。
Output
输出取余后的方案数
Sample Input
5
1 30000
2 30000
3 30000
4 30000
5 30000
Sample Output
1
3
11
70
629