#include <fstream>

using namespace std;
//long v[1000001][2];
int main()
{ifstream f("divprim.in");
ofstream g("divprim.out");
int i,cod=0,j,l,k=0,s=0,q,t,o,co=0;;
long n;
f>>t;
for(q=1;q<=t;q++)
{
co=0;
f>>n;
f>>o;

for(i=n;i>=1;i--)
{s=0;
    for(j=2;j<=i;j++)
    {cod=0;
    if(i%j==0){
    for(l=2;l*l<=j;l++)
    if(j%l==0) {cod=1;break;}
    if(cod==0) s++;
    }
    }
    cod=0;
if(o==s) {g<<i<<'\n';co=1;break;}
  //  k++;
   // v[k][1]=i;v[k][2]=s;
  //  g<<"v["<<k<<"][1]="<<i<<";"<<endl;
 //   g<<"v["<<k<<"][2]="<<s<<";"<<endl;

}
if(co==0) g<<0<<endl;
}
    return 0;
}