#include <cstdio>

using namespace std;
int w[1000005],cw[10][1000005];
int main()
{
    //cout << "Hello world!" << endl;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int n,a,b,mi;
    long long int i,j;
    //pr1[1]=2;
    for (i=2; i<=1000000; i=i+2)
    {
        if (w[i]==0)
        {
            //con++;
            //w[i]=1;
            for (j=i; j<=1000000; j=j+i)
                w[j]++;
        }
        if (i==2)
            i--;
    }
    int con1=0,con2=0,con3=0,con4=0,con5=0,con6=0,con7=0;
    int k;
    cw[0][1]=1;
    for (k=2;k<=1000000;k++)
        {
            if (w[k]==1)
            {
                con1++;
                cw[1][con1]=k;
            }
            if (w[k]==2)
            {
                con2++;
                cw[2][con2]=k;
            }
            if (w[k]==3)
            {
                con3++;
                cw[3][con3]=k;
            }
            if (w[k]==4)
            {
                con4++;
                cw[4][con4]=k;
            }
            if (w[k]==5)
            {
                con5++;
                cw[5][con5]=k;
            }
            if (w[k]==6)
            {
                con6++;
                cw[6][con6]=k;
            }
            if (w[k]==7)
            {
                con7++;
                cw[7][con7]=k;
            }
        }
    scanf("%d",&n);
    for (k=1;k<=n;k++)
    {
        scanf("%d%d",&a,&b);
        int st=1,dr;
        if (b==0)
            dr=1;
        if (b==1)
            dr=con1;
        if (b==2)
            dr=con2;
        if (b==3)
            dr=con3;
        if (b==4)
            dr=con4;
        if (b==5)
            dr=con5;
        if (b==6)
            dr=con6;
        if (b==7)
            dr=con7;
        int pp=0;
        while (st<=dr)
        {
            mi=(st+dr)/2;
            if (cw[b][mi]<=a)
            {
                st=mi+1;
                pp=cw[b][mi];
            }
            else
                dr=mi-1;
        }
        printf("%d\n",pp);
    }
    return 0;
}