背景

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既四种