#include <fstream>

using namespace std;

int main()
{ int n,i,st,mij,dr,nr,k,j,div;
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    f>>n;
    for (i=1;i<=n;++i) {
        f>>dr>>k;
        st=0;
        int Max=0;
        for (j=dr;j>=0;--j) {
            div=2;
            mij=j;
            nr=0;
            while (mij>1) {
                if (mij%div==0) {
                    ++nr;
                    while (mij%div==0)
                        mij/=div;
                }
                ++div;
            }
            if (nr==k || j==0) {
                g<<j<<"\n";
                break;
            }
        }
      }
    return 0;
}