#include <fstream>

using namespace std;
int v[1000000];
ifstream cin("divprim.in");
ofstream cout("divprim.out");
void ciur()
{
    for(int i=2;i<1000000;i++)
    {
        if(v[i]==0)
        {

            for(int j=i;j<1000000;j+=i)
                v[j]++;
        }
    }
}
int main()
{
    int n,a,b,rez=0;
    cin>>a;
    ciur();
    for(int i=0;i<a;i++)
    {
        rez=0;
        cin>>n>>b;
        for(int i=n;i>1;i--)
        {
            if(v[i]==b)
            {
              rez=i;
              break;
            }
        }
        cout<<rez<<"\n";
    }
    return 0;
}