## CERI2018L - Number of divisors of factorial

no tags

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$.

hide comments wisfaq: 2018-05-08 14:38:25 whom should be whose (whose is the genitive) =(Francky)=> Corrected ; thanks again. Last edit: 2018-05-08 14:55:34

 Added by: Francky Date: 2018-05-08 Time limit: 10s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All