#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e6;
int all[8][N + 5];
bool ciur[N + 5];
int nrdiv[N + 5];

void sieve(){
    int i,j;
    for(i = 2;i <= N;i++){
        if(ciur[i] == 0){
            nrdiv[i] = 1;
            for(j = 2*i;j <= N;j += i){
                nrdiv[j]++;
                ciur[j] = 1;
            }
        }
        if(nrdiv[i] <= 8){
            all[nrdiv[i]][++all[nrdiv[i]][0]] = i;
        }
    }
}

int binarySearch(int lf, int k, int x){
    int rg = all[k][0];
    int i,step;
    for(step = 1;step <= rg;step <<= 1);
    for(i = lf-1;step;step >>= 1){
        if(i + step <= rg && all[k][i + step] <= x){
            i += step;
        }
    }
    if(i == 0){
        return 0;
    }
    return all[k][i];
}

int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    sieve();
    int test,T,n,k;
    scanf("%d", &T);
    for(test = 1;test <= T;test++){
        scanf("%d %d", &n, &k);
        if(k == 0){
            printf("1\n");
            continue;
        }
        printf("%d\n", binarySearch(1, k, n));
    }
    return 0;
}