///Nume:Petre Vlad
///Scoala: C.N.I. "Grigore Moisil"Brasov
///Clasa: a X-a
///Email: [email protected]
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int main()
{
    int t,nr,a[100],n,k,d,x;
    fin>>t;


for(int i=1;i<=t;i++)
{  fin>>n>>k;
x=0;
    for(int j=1;j<=n;j++)
    {a[j]=j;
nr=0;
    int q=a[j];
    if(q%2==0)
        nr++;

    for(d=3;d<q;d+=2)
    {
        if(q%d==0)
        {
            nr++;
            q=q/d;
        }
    }
    if(nr==k)
    x=a[j];
}
fout<<x<<"\n";
}

    return 0;
}