#P2155. [SDOI2008] 沙拉公主的困惑

    ID: 1173 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数论数学2008各省省选山东素数判断质数筛法逆元

[SDOI2008] 沙拉公主的困惑

题目描述

大富翁国因为通货膨胀,以及假钞泛滥,政府决定推出一项新的政策:现有钞票编号范围为 11NN 的阶乘,但是,政府只发行编号与 M!M! 互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在,请你帮助沙拉公主解决这个问题,由于数量可能非常大,你只需计算出答案对 RR 取模后的结果即可。

输入格式

第一行为两个整数 TTRR,其中 TT 为该组中测试数据数目,RR 为模数。

接下来 TT 行,每行一对整数 NNMM,具体意义见题目描述。

输出格式

TT 行,对于每一对 NNMM,输出 [1,N!][1, N!] 中与 M!M! 互质的数的数量对 RR 取模后的值。

1 11
4 2
1

提示

对于 100%100\% 的数据,1MN1071\leq M\leq N\leq 10^71T1041\leq T\leq 10^42R109+102\leq R\leq 10^9+10RR 为质数。