#include <cstdio>
#include <bitset>
#include <math.h>
#define NMAX 1000010

using namespace std;

bitset <NMAX> b;

long f [NMAX];
long dp [8][NMAX];

void Eratostene () {
    long i , j , lim , lim2;
    lim = NMAX - 10;
    lim2 = sqrt (lim);
    b.set (0);
    b.set (1);
    for (j = 4 ; j <= lim ; j += 2) {
        b.set (j);
        f [j] ++;
    }
    for (i = 3 ; i <= lim2 ; i = i + 2)
        if (b.test(i) == 0) {
            for (j = i + i; j <= lim ; j += i) {
                b.set (j);
                f [j] ++;
            }
            f [i] ++;
        }
    for (i = 1 ; i <= lim ; i ++)
        dp [f [i]][++ dp [f[i]][0]] = i;
}


long Solve (const long &N , const long &K) {
    long step , i;
    for (step = 1 ; step < dp [K][0] ; step <<= 1);
    for (i = 0 ; step ; step >>= 1)
        if (i + step <= dp [K][0] && dp [K][i + step] <= N)
            i += step;
    return i;
}

int main () {
    long Tests , testcase , N , K , rez;

    freopen ("divprim.in" , "r" , stdin);
    freopen ("divprim.out" , "w" , stdout);

    Eratostene ();
    scanf ("%ld" , &Tests);
    for (testcase = 1 ; testcase <= Tests ; testcase ++) {
        scanf ("%ld%ld" , &N , &K);
        rez =  Solve (N , K);
        if (rez != 0)
            rez = dp [K][rez];
        printf ("%ld\n" , rez);
    }
    return 0;
}