#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+=2)
        ciur[i]++;
    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;
        bool ok=0;
        for(int i=n;i>=1;i--)
        {
            if(ciur[i]==k)
            {
                cout<<i<<endl;
                ok=1;
                break;
            }

        }
        if(ok==0)
            cout<<0<<endl;

        t--;
    }
    return 0;
}