Problem1946--凑数

1946: 凑数

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

任何数都存在唯一质因数分解,n!也不例外。
cjm在完全分解 n!之后,为了得到更多的k就将这些质数分组,比如6!=24×32×5=(2×3)×(2×3)×2×2×5,这样最多可以得到2个6。
cjm想知道分组之后最多可以得到多少个k

Input

第一行一个整数T (T≤30)表示数据的组数,紧接着有T行输入数据

每组数据占一行,包含两个整数n,k (1≤n,k≤108

Output

每组数据输出一个整数

Sample Input Copy

1
6 6

Sample Output Copy

2