#include<cstdio>

using namespace std;

bool ok[1000001];
int n,t,kt,kdiv[1000001],k;

void ciur()
{       int i,j;
        for(i=2;i*i<=1000000;i++)
                if(ok[i])
                {       j=2;
                        while(i*j<=1000000)
                        {       ok[i*j]=false;
                                j++;
                        }
                }
}
int main()
{       int i,j;
        freopen("divprim.in","r",stdin);
        freopen("divprim.out","w",stdout);
        for(i=1;i<=1000000;i++) ok[i]=true;
        ciur();
        for(i=2;i<=1000000;i++)
        {       for(j=2;j<=i/2;j++)
                        if(ok[j]&&i%j==0) kdiv[i]++;
                if(ok[i]) kdiv[i]++;
        }
        kdiv[1]=0;
        scanf("%d",&t);
        for(kt=1;kt<=t;kt++)
        {       scanf("%d%d",&n,&k);
                for(i=n;i>=2;i--)
                        if(kdiv[i]==k) {printf("%d\n", i);break;}
                if(i<2) printf("0\n");
        }
        return 0;
}