#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
const int vmax=1000001;
int ciur[1000001];
void Ciur()
{
    for(int i=2;i<=vmax;i++)
    {
        if(ciur[i]==0)
        for(int j=i;j<=vmax;j+=i)
        {
            ciur[j]++;
        }
    }
}
int main()
{
    Ciur();
    int n, k, t;
    cin>>t;
   //cout<<ciur[3]<<" "<<ciur[6]<<endl;
    while(t)
    {
        cin>>n>>k;
        while(ciur[n]!=k && n>=1)
            n--;
        cout<<n<<endl;
        t--;
    }
    return 0;
}