Find the number of divisors of N! (factorial) very fast !

Input

The first line contains an integer T, the number of test cases.

Each line of the next T lines contains two integers N and M.

Output

For each line, output a single line containing the number of divisors of N! modulo M.

Example

Input

3
10 989
10000 999989
10000000000 999999999989

Output

270
616797
40946947081

Constraints

1 ≤ T ≤ 10⁴
0 ≤ N ≤ 10¹¹
1 ≤ M ≤ 10¹²

Information

There are 5 input files.

- Input #1: T ≤ 10⁴, N ≤ 10⁴, TL = 1s

- Input #2: T ≤ 5, N ≤ 10⁸, TL = 20s

- Input #3: T ≤ 5, N ≤ 10⁹, TL = 20s

- Input #4: T ≤ 5, N ≤ 10¹⁰, TL = 20s

- Input #5: T ≤ 5, N ≤ 10¹¹, TL = 20s

My total running time is 3.14 sec. (C++)

Credits

• ivar.raknahs - the original problem (DIVFACT) author
• Francky - the author of DIVFACT2 and DIVFACT3