#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1000005;

int ans[8][NMAX],
         c[NMAX];

inline void erat(int lim) {
    int i, j, t;

    for(i=2; i<=lim; i+=2)
        ++c[i];
    for(i=3; i<=lim; i+=2) {
        if(c[i])
            continue;
        for(j=i; j<=lim; j+=i)
            ++c[j];
    }
    for(i=2; i<=lim; ++i)
        if(c[i]<=7)
            ans[c[i]][i]=i;
    for(i=1; i<=7; ++i)
        for(j=2; j<=lim; ++j)
            if(!ans[i][j])
                ans[i][j]=ans[i][j-1];
}

int main(void) {
    FILE *fi = fopen("divprim.in","r");
    FILE *fo = fopen("divprim.out","w");
    int t, n, k;

    erat(NMAX-5);

    fscanf(fi,"%d",&t);
    while(t--) {
        fscanf(fi,"%d%d",&n,&k);
        fprintf(fo,"%d\n",ans[k][n]);
    }

    fclose(fi);
    fclose(fo);
    return 0;
}