#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int n,i,k,t,m[8][1000001],nr[8],st,dr,mij;
int c[1000001];
void ciur();
int cautare();

int main()
{
    ciur();
    fin>>t;
    for(i=1; i<=t; ++i)
    {
        fin>>n>>k;
        st=0;
        dr=nr[k];
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(m[k][mij]>n) dr=mij-1;
            else st=mij+1;
        }

        fout<<m[k][dr]<<"\n";

    }

    return 0;
}



void ciur()
{

    for(int i=2; i<=1000000; i++)
    {
        if(c[i]==0)
        {
            for(int j=i; j<=1000000; j+=i)
                c[j]++;
        }

        m[c[i]][++nr[c[i]]]=i;
    }
}