#include <fstream>
#include <vector>
#define DIM 1000005
using namespace std;

int c[DIM];
vector<int> d[8];

void sieve() {
    d[0].push_back(1);
    for(int i=2;i<=DIM;i++) {
        if(c[i]==0)
        for(int j=i;j<=DIM;j+=i)
            c[j]++;
        if(c[i]<=7)
            d[c[i]].push_back(i);
    }
}

int findNumber(int n, int k) {
    int st=0,dr=d[k].size()-1,mij,ans=0;
    while(st<=dr) {
        mij=(st+dr)/2;
        if(d[k][mij]<=n)
            ans=d[k][mij],st=mij+1;
        else
            dr=mij-1;
    }
    return ans;
}

int main()
{
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    sieve();
    int t,n,k;
    fin>>t;
    for(int i=0;i<t;i++) {
        fin>>n>>k;
        fout<<findNumber(n,k)<<'\n';
    }
    return 0;
}