#include<iostream.h>
#include<conio.h>
#include<fstream.h>
#include<math.h>
int nr_div(int n)
{
int nr=0;
int m=n;
int i=2;
while(i<=n/2)
{
int k=0;
while (m%i==0){ m=m/i;k++;}
if (k!=0) nr++;
i+2;
}
return nr;
}

int main()
{
short k;
long t,n;
ifstream f;
ofstream g;
clrscr();
int x=0,ok;
f.open("divprim.in",ios::in);
g.open("divprim.out",ios::out);
f>>t;
//cout<<t<<endl;
//f<<endl;
while(!f.eof())
{
f>>n>>k;
//cout<<n<<"->"<<k<<endl;
for (int i=n;i>=2;i--)
{  ok=0;
if (nr_div(i)==k)
{
g<<i<<endl;
ok=1;
break;
}
}
if (ok==0) g<<0<<endl;
x++;
if (x==t) break;
}
f.close();
g.close();
cout<<"Rezultatul a fost scris in fisierul FISIER.OUT"<<endl;
getch();
return 0;
}