无额外样例文件。

题目描述

已知 f(a,b) 表示 1, 2, 3, ……, a 中与 b 互质的数的个数。

例如 f(6, 2) = 3，因为 1, 2, 3, ……, 6 中与 2 互质的数有：1, 3, 5 共 3 个。

现在给出两个整数 n, m, 求 f(n!, m!)。

多组数据。由于答案可能很大，你只需输出每组数据的答案 mod p 的值，其中 p 是一个给定的质数。

输入格式

第一行：包含两个整数 $T, p$, 分别表示数据组数与模数。

接下来 $T$ 行，每行包含两个整数 $n, m$。

输出格式

共 $T$ 行，每组数据的答案占一行。

样例输入

5 4658597
3 2
621367 528597
815813 610872
913449 228621
395263 292200

样例输出

3
2962401
2302816
471852
1355196

样例解释

此处仅解释第一组样例数据：n=3, m=2

3!=6, 2!=2

f(3!, 2!) = f(6, 2) = 3

数据范围

100% 的数据：$1 ≤ m ≤ n ≤ 10^7$，$1 ≤ T ≤ 10^4$，$2 ≤ p ≤ (1e9+10)$ 且 $p$ 为质数。