#include <stdio.h>
#define DIM 10000
char buff[DIM];
int poz=0;
void citeste(int &numar)
{
     numar = 0;     
     while (buff[poz] < '0' || buff[poz] > '9')     
          if (++poz == DIM) 
               fread(buff,1,DIM,stdin),poz=0;         
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM) 
               fread(buff,1,DIM,stdin),poz=0;               
     }     
}
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;
    citeste(t);
    for(int x=1;x<=t;x++)
    {
            citeste(n);
            citeste(k);
            ciur[0]=k;
            for(int i=n;i>=0;i--)
            {
                    if(ciur[i]==k)
                    {
                        printf("%d\n",i);
                        break;
                    }
            }
    }
}