#include <cstdio>
#include <cmath>
using namespace std;
bool c[1005];
int p[200];
int t,n,k,cnt;
void ciur(int n)
{
    int lim,i,j;
    c[0]=c[1]=1;
    lim =(int)sqrt((double)n);
    for(i=4; i<=n; i+=2)
        c[i]=1;
    for(i=3; i<=lim; i+=2)
        if(!c[i])
            for(j=i*i; j<=n; j+=2*i)
                c[j]=1;
}
int div(int nr)
{
    int d=0;
    for(int i=1; i<=cnt; i++)
        if(nr%p[i]==0) d++;
    return d;
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    ciur(1000);
    for(int i=1; i<=1000; i++)
        if(!c[i]) p[++cnt]=i;
    int nr;
    scanf("%d",&t);
    while(t)
    {
        t--;
        scanf("%d%d",&n,&k);
        nr=n;
        while(nr)
        {
            if(div(nr)==k) break;
            nr--;
        }
        printf("%d\n",nr);
    }
    return 0;
}