题目详情 - 阶乘因式分解（二） - 南阳理工学院OJ

ID: 167

远端评测题

3000ms

128MiB

难度: (无)

上传者:

给定两个数n，m,其中m是一个素数。

将n（0<=n<=2^31）的阶乘分解质因数，求其中有多少个m。

注：^为求幂符号。

Input

第一行是一个整数s（0<s<=100)，表示测试数据的组数
随后的s行, 每行有两个整数n，m。

Output

输出m的个数

Sample Input

3
100 5
16 2
1000000000  13

Sample Output

24
15
83333329

HINT

Source