#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()
{
    for(i=2;i<=1000000;i++)if(!a[i]){for(j=i;j<=1000000;j=j+i)a[j]++;}
    km[1]=2;km[2]=6;km[3]=30;km[4]=210;km[5]=2310;km[6]=30030;km[7]=510510;
    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--);
            g<<j<<'\n';
        }
    }
}