1436: ShacozzZ 的 QQ 密码

ShacozzZ 有很多个 QQ 号，每个 QQ 号的密码都是一个数字，但是最后 ShacozzZ 把所有的 QQ 号的密码都忘记了。

于是 ShacozzZ 找到了全知全能的神请求他告诉 ShacozzZ 他的 QQ 号密码。

而神对于每个 QQ 号，神给了 ShacozzZ 两个数字 $x$ 和 $y$，并告诉 ShacozzZ 他的 QQ 号的密码就是将 $x$ 分解成 $y$ 个数字的乘积的形式有多少种分法，需要注意的是 $1 * 2$ 和 $2 * 1$ 是两种不一样的分法。

第一行包含一个整数 $n$，即 ShacozzZ 的 QQ 号个数。

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

输出包含 $n$ 行，每行一个整数，即 ShacozzZ 的 QQ 号密码。

2
6 2
36 3

4
36

$1 \le n \le 2e5$

$1 \le x \le 1e9$

$1 \le y \le 20$