#include<fstream>
using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int k,n,i,x,y,d,m,t,j;


int main(){
    fin>>t;
    for(j=1; j<=t; j++){
        fin>>n>>k;
        m=0;
        for(i=n;i>0;i--){
            x=i;
            y=0;
            for(d=2;d<=x;d++){
                if(x%d==0)
                    y++;
                while(x%d==0){
                    x=x/d;
                }
            }
            if(y==k){
                m=i;
                break;
            }
        }
        fout<<m<<"\n";
    }
}