#include <cstdio>
#define DIM 500001
using namespace std;

FILE *fin = fopen("divprim.in" ,"r");
FILE *fout= fopen("divprim.out","w");

int D[8][DIM], N, Frec[DIM], P[DIM];

void Sieve(){
    Frec[0] = Frec[1] = 1;
    for(int i = 4; i < DIM; i += 2)
        Frec[i] = 1;
    P[++P[0]] = 2;
    for(int i = 3; i < DIM; i += 2)
        if(Frec[i] == 0){
            P[++P[0]] = i;
            for(int j = i + i + i; j < DIM; j += i + i)
                Frec[j] = 1;
        }
    return;
}

void SetUp(){
    int nr, val;
    for(int i = 1; i < DIM; i ++){
        nr = 0, val = i;
        for(int j = 1; P[j] <= val && Frec[val]; j ++)
            if(val % P[j] == 0){
                nr ++;
                while(val % P[j] == 0)
                    val /= P[j];
            }
        if(!Frec[val]) nr ++;
        D[nr][++D[nr][0]] = i;
    }
    return;
}

void CautBin(int N, int K){
    int st = 1, dr = D[K][0];
    while(st <= dr){
        int mid = st + (dr - st) / 2;
        if(D[K][mid] <= N)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    int val = 0;
    if(dr != 0) fprintf(fout, "%d\n", D[K][dr]);
    if(dr == 0) fprintf(fout, "%d\n", val     );
    return;
}

void CodeExpert(){
    int Q, N, K;
    fscanf(fin, "%d ", &Q);
    for(Q = Q; Q >= 1; Q --){
        fscanf(fin, "%d %d ", &N, &K);
        CautBin(N, K);
    }
    return;
}

void Test(){
    for(int i = 1; i <= 100; i ++){
        fprintf(fout, "%d %d %d %d %d %d %d %d\n", D[0][i], D[1][i], D[2][i], D[3][i], D[4][i], D[5][i], D[6][i], D[7][i]);
    } return;
}

int main(){
    Sieve();
    SetUp();
    //Test();
    CodeExpert();
    return 0;
}