#3057. 密码(组合数,欧拉筛,质因数分解)

密码(组合数,欧拉筛,质因数分解)

背景

lzh有很多个QQ号,每个QQ号的密码都是一个数字,但是最后lzh把所有的QQ号的密码忘了. 于是lzh找到了全知全能的神请求他告诉lzh他的QQ号密码。 而神对于每个QQ号,神给了lzh两个数字x和y,并告诉他密码就是将x分解成y个数字的乘积的形式有多少种分法,需要注意的是1 * 2和2 * 1是两种不一样的分法。

输入

第一行一个整数n,就是qq的个数

接下来n行每行包含两个整数x和y,即神告诉lzh的两个数字。

输出

输出n行,每一行一个整数表示目前qq号的密码

样例

2
6 2
36 2
4
36

说明和提示

1<=n<=2e5 1<=x<=1e9 1<=y<=20 对于样例中的第一个密码,6 分成两个书数字乘积可以是6 1,1 6,2 3 ,3 2既四种