3360: 沙拉公主的困惑
内存限制：256 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。
输入
第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R为模,
后面T行，每行一对整数N，M，见题目描述
输出
共T行，对于每一对N，M，输出1至N！中与M！素质的数的数量对R取模后的值
样例输入 复制
1 11
4 2样例输出 复制
1提示
【数据范围】
对于20%的数据， 1<=N,M<=10,T<=10
对于40%的数据， 1<=N,M<=10000
对于80%的数据， 1<=N,M<=1000000
对于100%的数据，1<=N,M<=10000000