#include<iostream>
using namespace std;
#define int long long
const int N=12;
int n,m,k,t,c[N][N];
int solve()
{
    int cnt=0,tmp=0;
    for(int i=2;i<=n/i;i++)
        if(n%i==0)
        {
            cnt++;
            while(n%i==0)
                n/=i,tmp++;
        }
    if(n>1)
        cnt++,tmp++;
    if(cnt<k || cnt<tmp)
        return 0;
    return c[cnt-1][k-1];
}
signed main()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j)
                c[i][j]=1;
            else
                c[i][j]=c[i-1][j]+c[i-1][j-1];
    cin>>t;
    while(t--)
        scanf("%lld%lld",&n,&k),printf("%lld\n",solve());
}

思路感觉没问题，质因子拆解出来必须指数为1，而且这些质因子最多也不到10个，long long没爆，我只有质因子个数少于k或者存在指数大于1的质因子才会返回0