#include <stdio.h>

int ciur[1000000],nr[8],mat[8][1000000];
int caut(int v[],int n,int x)
{
    int i=0,pas=1<<19;
    while(pas!=0)
    {
        if(i+pas<=n&&v[i+pas]<=x)
            i+=pas;
        pas/=2;
    }
    return v[i];
}
int main()
{
    FILE*fin,*fout;
    int l,d,i,k,nrdiv,nrt;
    fout=fopen("divprim.out","w");
    fin=fopen("divprim.in","r");
    for(i=2;i<=1000000;i++)
        if(ciur[i]==0)
            for(d=i;d<=1000000;d+=i)
                ciur[d]++;
    ciur[1]=0;
    for(i=1;i<1000000;i++)
    {
        nrdiv=ciur[i];
        nr[nrdiv]++;
        mat[nrdiv][nr[nrdiv]]=i;
    }

    fscanf(fin,"%d",&nrt);
    for(i=0;i<nrt;i++)
    {
        fscanf(fin,"%d%d",&l,&k);
        fprintf(fout,"%d\n",caut(mat[k],nr[k],l));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}