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

int NR , t, v[11], p[RAD + 1], RQ[NMAX + 2][10];
bool f[RAD + 1];
inline int desc(int x){
    int i = 1, Rez = 0;
    while(p[i] < x && i <= NR){
        if(x % p[i] == 0){
            ++Rez;
            while(x % p[i] == 0)
                x /= p[i];
        }
        ++i;
    }
    if(x > 1) ++Rez;
    return Rez;
}
int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    scanf("%d", &t);
    p[++NR] = 2;
    for(int i = 3; i < RAD; i += 2){
        if(f[i] == 0){
            p[++NR] = i;
            for(int j = i * 3; j < RAD; ++j)
                f[j] = 1;
        }
    }
    int x, k;
    for(int i = 4; i <= 1000000; ++i){
        int NR = desc(i);
        v[NR] = i;
        RQ[i][1] = v[1];
        RQ[i][2] = v[2];
        RQ[i][3] = v[3];
        RQ[i][4] = v[4];
        RQ[i][5] = v[5];
        RQ[i][6] = v[6];
        RQ[i][7] = v[7];

    }

    for(int i = 1; i <= t ; ++i){
        scanf("%d%d", &x, &k);
        if(k == 0)
            {printf("1"); continue ;}
        printf("%d\n", RQ[x][k]);
    }
    return 0;
}