#include <fstream>
#include <cmath>
using namespace std;
short v[1000001];
void completam(int i)
{
    int j;
    for(j=i;j<=1000000;j+=i)
        v[j]+=1;
}
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int t,n,k,r,i,j;
    r=1000;
    for(i=2;i<=500000;i++)
    {
        if(v[i]==0)
            completam(i);
    }
    for(i=500001;i<=1000000;i++)
        if(v[i]==0)
            v[i]=1;
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>n>>k;
        if(k==0)
            g<<"1"<<'\n';
        else
        {
            j=n;
            while(v[j]!=k and j>1)
            {
                j-=1;
            }
            if(j>1)
                g<<j<<'\n';
            else
                g<<"0"<<'\n';
        }
    }
  /* for(i=1;i<=10;i++)
        g<<v[i]<<" "<<i<<'\n';*/
    f.close();
    g.close();
    return 0;
}