#include<stdio.h>
#define NMAX 1000000

int v[NMAX+2];

int main()
{
    
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    
    int i, j, t, n, k;
    
    for (i=2; i<=NMAX; i++)
    {
        if (!v[i])
            for (j=i; j<=NMAX; j+=i)
                ++v[j];
    }
    scanf("%d", &t);
    for (; t>0; t--)
    {
        scanf("%d %d", &n, &k);
        v[0]=k;
        //tre sa scad complexitatea aici
        for (i=n; i>=0; --i)
        if (v[i]==k)
        {
            printf("%d\n", i); 
            break;
        }
    }
    
    fclose(stdout);
    return 0;
}