#include <cstdio>
int n,i,a[100000],x[100003],y[100003],max,nrt,j,l,d,nr,aux,f,v[1000005],ok;
bool pp[1000004];
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    n++;
    a[n]=2;
    for(i=3;i<=1000000;i=i+2)
    {
        if(pp[i]==0)
        {
            n++;
            a[n]=i;
            for(j=i+i;j<=1000000;j=j+i)
                pp[j]=1;
        }
    }
    scanf("%d",&nrt);
    for(i=1;i<=nrt;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        if(max<x[i])max=x[i];
    }
    v[2]=1;
    for(i=3;i<=max;i++)
    {
        if(pp[i]==0&&i%2==1)v[i]=1;
        else
        {
            aux=i;
            nr=0;
            d=1;
            while(aux>1)
            {
                f=0;
                while(aux%a[d]==0)
                {
                    aux=aux/a[d];
                    f++;
                }
                if(f>0)nr++;
                d++;
            }
            v[i]=nr;
        }
    }
    for(i=1;i<=nrt;i++)
    {
        ok=0;
        for(j=x[i];j>=1;j--)
        {
            if(v[j]==y[i]){ok=1;printf("%d\n",j);break;}
        }
        if(ok==0)printf("0\n");
    }
    return 0;
}