#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out")
const int maxx=1e6;
vector<int>a[8];
void ciur()
{
    vector<int>div(maxx+1,0);
    for(int i=2;i<=maxx;i++)
    {
        if(!div[i])
        {
            for(int j=i;j<=maxx;j+=i)
            {
                div[j]++;
            }
        }
    }
    for(int i=2;i<=maxx;i++)
    {
        if(div[i]<=7)
        {
            a[div[i]].push_back(i);
        }
    }
}
int main()
{
     ciur();
     int q;
     cin>>q;
     while(q--)
     {
         int x,k;
         cin>>x>>k;
         int st=0,dr=a[k].size()-1,rez=0;
         while(st<=dr)
         {
            int m=(dr+st)>>1;
            if(a[k][m]<=x)
            {
                rez=a[k][m];
                st=m+1;
            }
            else
            {
                dr=m-1;
            }
         }
         cout<<rez<<'\n';
     }
}