题目描述

给定$n,k$，问有多少个长度为$k$的序列$a_i$满足：

• $\prod_{i=1}^{k}a_i=n$
• $lcm(a_1,a_2,…,a_k)=n$
• $1<a_1\leq a_2\leq a_3\leq …\leq a_k$

其中$lcm(a_1,a_2,…,a_k)$表示$a_1,a_2,…,a_k$的最小公倍数。

输入格式

第一行输入一个整数$T$，表示数据组数。 接下来$T$行，每行输入一组数据，包含两个整数$n,k$。

输出格式

输出共$T$行，每行输出一个整数，表示你的答案。

样例输入 #1

2
12 2
12 3

样例输出 #1

1
0

说明/提示

有$1\leq n,k\leq 10^7,1\leq T\leq 10^5$。