#include <iostream>
#include <fstream>
/** Nume :Voinescu David-Ioan
Scoala: Colegiul National Andrei Saguna
Email: [email protected]
Clasa a-10-a **/
int isprim(int x){
if (x<2 || x>2 && x%2==0)
    return 0;
    else for(int d=3;d*d<=x;d+=2)
        if(x%d==0)
        return 0;
    return 1;
}
int nrdiv(int y){
int nr=0;
for(int d=2;d<=y;d++)
    if(y%d==0 && isprim(d)==1)
        nr++;
        return nr;
}
using namespace std;

int main()
{ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t,n,k;
fin>>t;
while(t){
fin>>n>>k;
for(int i=n;i>=1;i--){
if(nrdiv(i)==k){
fout<<i<<endl;
break;}
if(i==1){
    fout<<0<<endl;
    break;}
}
t--;
}

    return 0;
}