#include <stdio.h>
unsigned char ciur[1000001];
int main()
{
    freopen ("divprim.in","r",stdin);
    freopen ("divprim.out","w",stdout);
    for(int i=2;i<=1000000;i++)
    {
            if(ciur[i]==0)
            {
                          ciur[i]=1;
                          for(int j=2;j<=1000000/i;j++) ciur[i*j]++;
            }
    }
    int t,n,k;
    scanf("%d",&t);
    for(int x=1;x<=t;x++)
    {
            scanf("%d%d",&n,&k);
            ciur[0]=k;
            for(int i=n;i>=0;i--)
            {
                    if(ciur[i]==k)
                    {
                        printf("%d\n",i);
                        break;
                    }
            }
    }
}