#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][7] = {{0}};

void init()
{
    int p = sqrt(MAX*1.0)+1;

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

}


int main()
{
    init();

    fscanf(in, "%d", &t);
    for ( int i = 0; i < t; ++i )
    {
        fscanf(in, "%d %d", &n, &k);
        while ( a[n] != k && n >= 1 )
            --n;
        if ( n >= 2 )
            fprintf(out, "%d\n", n);
        else
            fprintf(out, "%d\n", 0);
    }

	return 0;
}