#include <iostream>
#include <fstream>
using namespace std;
int T,t,N,n,K,k,ok,i,j;
int main()
{int max;
    ifstream fin ("divprim.in");
    ofstream fout("divprim.out");
    fin>>T;
    for(t=1;t<=T;t++){
            max=0;
            fin>>N>>K;
            for(n=2;n<=N;n++){
                k=0;
            for(i=2;i<=n;i++){ok=1;
                for(j=2;j*j<=i;j++) if(i%j==0){ok=0;break;}
                        if(n%i==0&&ok==1) k++;
            }
            if(k==K) max=n;
            }
            fout<<max<<endl;
    }
    return 0;
}