#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    int T,n,k,i,j,d,x,u,p,t;

    ifstream f("divprim.in");
    ofstream g("divprim.out");

f>>T;

    for(i=1;i<=T;i++){
       f>>n>>k;

     for(j=n;j>=1;j--){
       x=j;p=2;u=0;t=0;

       while(p<=x){
        if(x%p==0){u++;
         while(x%p==0)
          x/=p;}
        p++;}

    if(u==k){g<<j<<'\n';t=1;break;}}

    if(t==0)g<<"0"<<'\n';}

}