Description

Due to inflation and rampant counterfeiting, the government of the Monopoly Kingdom decides on a new policy: the serial numbers of existing banknotes range from $1$ to $N!$, but the government will issue only banknotes whose serial numbers are coprime to $M!$. Princess Shala, the largest real estate holder, wants to estimate the total number of genuine banknotes now. Please help Princess Shala solve this problem. Since the number can be very large, you only need to compute the answer modulo $R$.

Input Format

The first line contains two integers $T$ and $R$, where $T$ is the number of testdata in this set, and $R$ is the modulus.

The next $T$ lines each contain a pair of integers $N$ and $M$, as described above.

Output Format

Output $T$ lines. For each pair $N$ and $M$, output the number of integers in $[1, N!]$ that are coprime to $M!$, taken modulo $R$.

1 11
4 2

1

Hint

For $100\%$ of the testdata, $1 \le M \le N \le 10^7$, $1 \le T \le 10^4$, $2 \le R \le 10^9+10$, and $R$ is prime.

Translated by ChatGPT 5