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