#include <iostream>
#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
const int nr=1000001;
int v[nr];
void ciur()
{
    int i,j;
    for(i=2;i<nr;i++)
    {
        while(v[i]!=0)
            i++;
        for(j=i;j<=nr;v[j]++,j+=i);
    }
}
int main()
{
    int t,x,k,n,i,j;
    ciur();
    in>>t;
    for(i=0;i<t;i++)
    {
        in>>x>>k;
        n=0;
        for(j=x;j>1;j--)
            if(v[j]==k)
            {
                n=j;
                break;
            }
        out<<n<<"\n";
    }
    return 0;
}