#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];
int main()
{
    f>>T;
    for(i=2;i<=1000000;i++)if(!a[i])for(j=i;j<=1000000;j=j+i)a[j]++;
    //for(i=1;i<=100;i++)cout<<i<<' '<<a[i]<<endl;
    for(;T>0;T--)
    {
        f>>n>>k;
        for(j=n;j>1;j--)if(a[j]==k)break;
        if(j==1)j=0;
        g<<j<<'\n';
    }
}