游客 Signup | Login
中文 | En

1871 - 阶乘因式分解(一)

通过次数

0

提交次数

0

Time Limit : 3 秒 Memory Limit : 128 MB

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

将n(0<=n<=10000)的阶乘分解质因数,求其中有多少个m。

Input

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

Output

输出m的个数。

Examples

Input Format

2
100 5
16 2

Output Format

24
15