#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int n,m,T,i,j,k;
int a[1000006],km[8];
int main()
{
    T=1;
    for(i=2;i<=1000000;i++)if(!a[i]){if(T<=7){km[T]=i;T++;}for(j=i;j<=1000000;j=j+i)a[j]++;}
    T=1;
    for(j=1;j<=7;j++){T=T*km[j];km[j]=T;}
    //for(i=1;i<=7;i++)cout<<i<<' '<<km[i]<<endl;
    f>>T;
    for(;T>0;T--)
    {
        f>>n>>k;
        if(k==0)g<<1<<'\n';
        else if(n<km[k])g<<0<<'\n';
        else
        {
            for(j=n;a[j]!=k;j--);
            if(j==1)j=0;
            g<<j<<'\n';
        }
    }
}