#include<fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int a[1000002],m[8][1000002],s,d,mij,sol;
int i,n,k,j,t,ok;
int main()
{
    m[0][0]=1;
    m[0][1]=1;
    //conventie
    for(i=2;i<=1000000;i++)
    {
        if(a[i]==0)
        {
            for(j=i;j<=1000000;j=j+i)
            {
                a[j]++;
            }
        }
        m[a[i]][0]++;
        m[a[i]][m[a[i]][0]]=i;
    }
    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>n>>k;
        s=1;
        d=m[k][0];
        while(s+1<d)
        {
            mij=(s+d)/2;
            if(m[k][mij]<=n)
            {
                s=mij;
            }
            else
            {
                d=mij;
            }
        }
        if(m[k][1]>n)
        {
            fout<<0<<"\n";
        }
        else
        {
            fout<<m[k][s]<<"\n";
        }
    }
    fin.close();
    fout.close();
    return 0;
}