#include <cstdio>

using namespace std;

int diviz[500001], c[500001],p=1,n,t,k;

void ciur()
{
    c[1]=1;
    for(int i=2;i<=500000;i++)
    {
        if(c[i]==0)
        {
            diviz[p]=i;
            p++;
            for(int j=i+i;j<=500000;j+=i)
                c[j]=1;
        }
    }
    p--;
}

int nrdiv(int x, int y)
{
    int nr=0;
    for(int i=1;i<=p;i++)
    {
        if(x%diviz[i]==0)
            nr++;
        if(nr>y)
            return 0;
    }
    if(nr<y)
        return 0;

    return 1;
}

int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    scanf("%d\n", &t);
    ciur();
    for(int i=1;i<=t;i++)
    {
        scanf("%d %d\n", &n, &k);

        int ok=0;
        while(ok==0 && n>1)
        {
            n--;
            if(nrdiv(n,k)==1)
                ok=1;
        }
        if(ok==0)
            printf("0\n");
        else printf("%d\n", n);
    }

    return 0;
}