#include <fstream>

using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");

int n,t, k, i;
long long prim(long long x)
{
    int i;
    if(x<2)
        return 0;
    if(x%2==0 && x>2)
        return 0;
    if(x==2)
        return 1;
    for(i=3; i*i<=x; i=i+2)
        if(x%i==0)
		return 0;
           return 1;
}

void ciur(int x, int k)
{
    int p=1, nrdiviz=0 ,nr;
    while(x%2 == 0)
    {
        x/=2;
        nrdiviz++;
    }
    p=nrdiviz+1;
    for(int d=3; d*d <= x && nr <= k; d+=2)
    {
        nrdiviz=0;
        if(prim(d)==1)
        {
            nr++;
            continue;
        while(x%d == 0)
        {
            x/=d;
            nrdiviz++;
        }
        p*=(nrdiviz+1);
        }
    }
    if(x != 1)
        p*=2;
        g << p<<"\n";
}

int main()
{
   f >> t;
   for(i=1; i<=t; i++)
   {
       f >> n >> k;
       ciur(n, k);
   }

    return 0;
}