#include <stdio.h>
#include <vector>
#define DIM 10000
char buff[DIM];
int poz=0;
std::vector<int> cate[8];
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]++;
                          }
            }
    }
    for(int i=1;i<=1000000;i++)
    {
        cate[ciur[i]].push_back(i);
    }
    std::vector<int>::iterator it;
//    printf("%d ",*std::upper_bound(cate[1].begin(),cate[1].end(),10));
    int t,n,k;
    citeste(t);
    for(int x=1;x<=t;x++)
    {
            citeste(n);
            citeste(k);
            if(cate[k][0]<=n)
            {
                int pos=std::lower_bound(cate[k].begin(),cate[k].end(),n)-cate[k].begin()-1;
                printf("%d\n",cate[k][pos]);
            }
            else printf("0\n");
    }
}