#include<stdio.h>
using namespace std;
int  sw[1000001];int div[8][379723];
int main()
{
    int i,j,n,k,t;div[0][1]=1;div[0][0]=1;
    for(i=2;i<=1000000;++i)
    {   if(!sw[i])
        {sw[i]=1;for(j=i+i;j<=1000000;sw[j]++, j+=i);}
        div[sw[i]][0]++;
        div[sw[i]][div[sw[i]][0]]=i;
    }
    freopen("divprim.in","r",stdin);freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    for(;t;--t)
    {
        scanf("%d %d",&n,&k);
        if(div[k][1]<=n)
        {
            int m,dr=div[k][0],st=1;
            while(st<dr)
            {
                m=(st+dr)/2;
                if(div[k][m]<=n)
                    st=m+1;
                else dr=m;
            }
            m=(st+dr)/2;
            if(div[k][m]>n) --m;
            printf("%d\n",div[k][m]);
        }
        else printf("0\n");
    }
    fclose(stdin);fclose(stdout);
    return 0;
}