#include<fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int n,k,t;
int v[1000002];
int m[8][1000000];
void Eratostene()
{
   int i,j,k=0;
    for(i=2;i<=1000000;i++)
    {
        if(v[i]==0)
        {
            for(j=i;j<=1000000;j+=i)
                v[j]++;
        }
    }
    for(i=0;i<=1000000;i++)
        if(v[i]<=7)
        {

            m[v[i]][0]++;
            m[v[i]][m[v[i]][0]]=i;
        }

}

void binary_search()
{
    int st=1,dr=m[k][0],sol=0;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(m[k][mid]<n && m[k][mid]>sol)
        {
            sol=m[k][mid];
            st=mid+1;
        }
        if(m[k][mid]>=n)
            dr=mid-1;
    }
    g<<sol<<"\n";
}
void read()
{
    int i;
    f>>t;
    for(i=0;i<t;i++)
    {
        f>>n>>k;
        binary_search();
    }
}
int main()
{
    Eratostene();
    read();
}