#include <cstdio>

using namespace std;
int c[1000005];
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int N,K,T;
    int i,j,ok;

    N=1000000;
    for(i=2 ; i<=N ; i+=2) //Generam ciurul
        c[i]=1;
    for(i=3 ; i<=N ; i+=2)
        if( !c[i] )
            for(j=i ; j<=N ; j+=i)
                c[j]++;

    scanf("%d", &T);
    while(T)
    {
        ok=1;
        scanf("%d%d", &N, &K);
        T--;
        for(i=N ; i>=2 ; i--)
            if(c[i]==K )
        {
            printf("%d\n",i);
            ok=0;
            break;
        }
        if(ok)
            printf("0\n");
    }

    return 0;
}