#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=3;i<=vmax;i+=2)
    {
        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[10]<<endl;
    while(t)
    {
        cin>>n>>k;
        int cp;
        cp=ciur[n];
        if(n%2==0)
        cp++;
        while(cp!=k && n>=1){
            n--;
            cp=ciur[n];
            if(n%2==0)
                cp++;
        }
        cout<<n<<endl;
        t--;
    }
    return 0;
}