#include<iostream>
#include<fstream>
#include<vector>
#define nmax 1000000
using namespace std;

vector<int> v[8];
int cb(int k,int n)
{
    int l1,l2,sol=0;
    l1=0;
    l2=v[k].size()-1;
    while(l1<=l2)
    {
        int m=(l1+l2)/2;
        if(v[k][m]<=n)
        {
            sol=v[k][m];
            l1=m+1;
        }
        else
            l2=m-1;


    }
    return sol;

}
char ciur[nmax+2];
int main()
{
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
    v[0].push_back(1);
    int i,j,t,n,k;
    for(i=2;i<=nmax;i++)
    {
        if(ciur[i]==0){
            v[1].push_back(i);
            for(j=2;j<=nmax/i;j++)
                ciur[j*i]++;
        }
        if(ciur[i]<=7)
            v[ciur[i]].push_back(i);
    }
    cin>>t;
    for(int shp=1;shp<=t;shp++)
    {
        cin>>n>>k;
        cout<<cb(k,n)<<"\n";
    }
    return 0;
}