The goal of the problem is to compute the number of divisors of $\text{Factorial}(n)$.

Input

The first line of the input consist of a single integer number $t$ which determines the number of tests.

In each of next $t$ lines there is two integer numbers $n$ and $m$.

Constraints

• $0 < t < 10^2$ ;
• $0 < n < 2\times10^5$ ;
• $1 < m < 2\times10^9$.

Output

For each test case, print the number of divisors of $n! \pmod m$.

Example

Input:
3
2 1000
3 100
1234 1000000007

Output:
2
4
787315782

Explanation

For the first test case, $2! = 1\times2=2$, whose number of divisors is $2$.

For the second test case, $3! = 1\times2\times3=6$, whose number of divisors is $4$.