#include <cstdio>
#define NMAX 1000000
using namespace std;

int NR , t, RQ[10][NMAX + 2];
int f[NMAX + 1];
inline void CBIN(int n, int k){
    int st = 1, dr = RQ[k][0];
    while(st <= dr){
        int mid = st + (dr - st) / 2;
        if(RQ[k][mid] <= n)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    if(dr == 0) printf("0\n");
    else printf("%d\n", RQ[k][dr]);
    return ;
}
int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    scanf("%d", &t);
    for(int i = 2; i <= NMAX; ++i){
        if(f[i] == 0)
            for(int j = i ; j <= NMAX; j += i)
                ++f[j];
    }
    for(int i = 1; i <= NMAX; ++i)
        RQ[f[i]][++RQ[f[i]][0]] = i;
    int x , k;
    for(int i = 1; i <= t ; ++i){
        scanf("%d%d", &x, &k);
        if(k == 0)
            {printf("1\n"); continue ;}
        CBIN(x, k);
    }
    return 0;
}