#include <cstdio>
#include <cmath>
#define MAX 1000001

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


int t, n, k;

int a[MAX+1] = {0};
int sol[MAX][8] = {{0}};

void init()
{
    for ( int i = 2; i <= MAX; i += 2 )
        ++a[i];

    for ( int i = 3; i <= MAX; i += 2 )
    {
        if ( !a[i] )
        {
            ++a[i];
            for ( int j = (i<<1); j <= MAX; j += i )
                    ++a[j];
        }
    }

    for ( int i = 0; i <= 7; ++i )
        sol[2][a[i]] = i;
    for ( int i = 3; i < MAX; ++i )
    {
        for ( int j = 0; j <= 7; ++j )
            sol[i][j] = sol[i-1][j];
        sol[i][a[i]] = i;
    }
}


int main()
{
    init();

    fscanf(in, "%d", &t);
    for ( int i = 0; i < t; ++i )
    {
        fscanf(in, "%d %d", &n, &k);
        fprintf(out, "%d\n", sol[n][k]);
    }

	return 0;
}