#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define NMAX 1000005
using namespace std;
char nrprim[NMAX];
int divprimi[80000];
void prim()
{int i,j;

    for (i=1;i<=NMAX;i++)
    nrprim[i]=1;
   int  ct=0;
    for (i=2;i<=NMAX;i++)
       if ((nrprim[i]) )
    
        {
         divprimi[++ct]=i;
        
        for (j=2*i;j<=NMAX;j+=i)
        nrprim[j]=0;
        }}
int nrdiv(int n)
 {int ct=0;
  for(int i=1;divprimi[i]<=sqrt(n);i++)
   {if(n%divprimi[i]==0)
    {ct++;
     while(n%divprimi[i]==0) 
       n=n/divprimi[i];}}
    if(n>1) ct++;   
   return ct;           
              }       
 
int main()
{int ct,n,k,t,j,i,ok;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    prim();
    
    for (i=1;i<=t;i++)
    {
        scanf("%d %d",&n,&k);
    
    ok = 0;ct=0;
    for (j=n;j>=2;j--)
    {
    ct=nrdiv(j);
    if (ct == k)
    {
           ok = 1;
           printf("%d\n",j);
           break;
    }
    }
    if (ok==0) printf("0\n");
    }
    
return 0;
}