#include<stdio.h>

using namespace std;

#define MAXN 1000002
#define MAXK 9

int T, N, K, i, j, nr;
int m[ MAXN ];
int A[ MAXN ][ MAXK ];

inline void Eratosthenes()
{
    int i, j;

    for(i = 2; i < MAXN; i += 2)
        m[i] = 1;
    for(i = 3; i < MAXN; ++i)
        if(!m[i])
        {
            for(j = i; j < MAXN; j += i)
                ++m[j];
        }
}

int main()
{
    FILE *f, *g;

    f = fopen("divprim.in", "r");
    g = fopen("divprim.out", "w");

    Eratosthenes();
    for(i = 1; i < MAXN; ++i)
    {
        for(j = 0; j <= 8; ++j)
            A[i][j] = A[i-1][j];
        A[i][ m[i] ] = i;
    }

    fscanf(f, "%d", &T);
    while(T)
    {
        fscanf(f, "%d %d", &N, &K);

        fprintf(g, "%d\n", A[N][K]);

        --T;
    }

    fclose(f);
    fclose(g);

    return 0;
}