DIVFACT3 - Divisors of factorial (hard)

求出阶乘数因子的个数 输入的第一行有是一个整数 $T$，表示该测试点有 $T$ 组数据。 接下来 $T$ 行，每一行两个整数 $N,M$，你需要求出 $N!$ 的因子个数，由于答案可能会很大，对 $M$ 取模后输出。 每组数据输出一行一个整数表示你的答案 $1\le T < 5432$， $1< N<10^8$， $1 < M < 10^9$

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

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

3
2 1000
3 11
4 5

2
4
3