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

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

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

int findNumber(int n, int k) {
    int st=0,dr=d[k].size(),mij,ans=0;
    while(st<=dr) {
        mij=(st+dr)/2;
        if(d[k][mij]==n)
            return mij;
        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;
}