#include <fstream>
#include <vector>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
const int lim=1e6;
vector<int> v[10];
int cnt[lim+3];
void compute()
{
    cnt[1]=0;
    v[0].push_back(1);
    for(int i=2;i<=lim;++i)
    if(!cnt[i])
    {
        cnt[i]=1;
        v[1].push_back(i);
        for(int j=2*i;j<=lim;j+=i)
            cnt[j]++;
    }
    else if(cnt[i]<=7)
        v[cnt[i]].push_back(i);
}
int bs(int n,int k)
{
    if(v[k].size()==0) return 0;
    if(n<v[k][0]) return 0;
    int l=0,r=v[k].size()-1,med;
    while(l<r)
    {
        if(r==l+1)
            med=r;
        else med=(l+r)/2;
        if(v[k][med]<=n)
            l=med;
        else r=med-1;
    }
    return v[k][l];
}
int main()
{
    int tst,n,k;
    compute();
    cin>>tst;
    for(int w=1;w<=tst;++w)
    {
        cin>>n>>k;
        cout<<bs(n,k)<<'\n';
    }
    return 0;
}