Description

给定询问组数 $T$ 和取模数 $R$ ，每次询问给定两个整数$n$和$m$ ( $m \le n$ )，求 $1-n!$ 的数中与 $m!$ 互质的数的个数。答案对 $R$ 取模，$R$ 是质数。

Input Format

第一行为两个整数$T$，$R$ 表示该组中测试数据数目，$R$ 为模数。

后面 $T$ 行，每行一对整数$n$ ，$m$ ， $m \le n$。

Output Format

共 $T$ 行，表示答案。

Sample

【输入样例】

1 11
4 2

【输出样例】

1

Hint

对于$100\%$的数据，$R \le 10^9+10$ ，$T \le 10000$，$1 \le N , M \le 10000000$

数据有梯度。