Factorial numbers are getting big very soon, you'll have to compute the number of divisors of such highly composite numbers.

Input

The first line contains an integer T, the number of test cases.
On the next T lines, you will be given two integers N and M.

Output

Output T lines, one for each test case, with the number of divisors of the factorial of N.
Since the answer can get very big, output it modulo M.

Example

Input:
3
2 1000
3 11
4 5
Output:
2
4
3

Constraints

0 < T < 512
1 < N < 10^8
1 < M < 10^9

For N, M : uniform random input in the range.
One input file.

Information

Time limit is sqrt(T_good.py × T_bad.c). It implies that you can solve it with some interpreted languages with correct algorithm without any optis, but will get TLE with fast languages and non optimal algorithm.
Good luck and have fun ;-)

(Edit 2017-02-11 : TL updated ; compiler changes)