#include <cstdio>
#define DIM 1000001
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(){
    for(int i = 2; i < DIM; i ++)
        if(Frec[i] == 0){
            for(int j = i; j < DIM; j += i)
                Frec[j] ++;
        }
    return;
}

void SetUp(){
    for(int i = 1; i < DIM; i ++)
        D[Frec[i]][++D[Frec[i]][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 ", Frec[i]);
    }   fprintf(fout, "\n "); return;
}

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