#include <cstdio>
int v[8][1000001],ciur[1000001];
void ciuruire(){
    int p,i;
    v[0][0]=2;
    v[0][1]=0;
    v[0][2]=1;
    for (p=2;p*2<=1000000;p++)
        if (ciur[p]==0){
            ciur[p]++;
            for (i=p*2;i<=1000000;i+=p)
                ciur[i]++;
        }
}
int main (){
    freopen ("divprim.in","r",stdin);
    freopen ("divprim.out","w",stdout);
    int n,i,nr,k,l1,l2,m,poz;
    ciuruire ();
    for (i=2;i<=1000000;i++){
        if (ciur[i]==0)
            ciur[i]++;
        v[ciur[i]][0]++;
        v[ciur[i]][v[ciur[i]][0]]=i;
    }
    scanf ("%d",&n);
    for (i=1;i<=n;i++){
        poz=0;
        scanf ("%d %d",&nr,&k);
        l1=1;
        l2=v[k][0];
        while (l1<=l2){
            m=(l1+l2)/2;
            if (v[k][m]<=nr){
                poz=m;
                l1=m+1;
            }
            else
                l2=m-1;
        }
        if (poz)
            printf ("%d\n",v[k][poz]);
        else
            printf ("0\n");
    }
    return 0;
}