#include <fstream>
using namespace std;

int st,dr,mij,x=0,i,j,t,k=0,n,mat[8][380000],l[8]={0,0,0,0,0,0,0,0};
void ciur()
{ 
    short v[1000005]; 
    for (i=1;i<= 1000000;i++)
     v[i]=0; 
    for(i=2;i<= 1000000;i++)
     if(v[i]==0)
     {
      for(j=2*i;j<= 1000000;j=j+i)
        ++v[j];
      v[i]=1;
      }    
     for (i=2;i<= 1000000;i++)
     switch(v[i])
      {                                           
        case 1: mat[1][l[1]++]=i;
             break;
        case 2: mat[2][l[2]++]=i;
             break;
        case 3: mat[3][l[3]++]=i;
             break;
        case 4: mat[4][l[4]++]=i;
             break;
        case 5: mat[5][l[5]++]=i;
             break;
        case 6: mat[6][l[6]++]=i;
             break;
        case 7: mat[7][l[7]++]=i;
             break;
      }  
}
int main()
{
    ciur();
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    f>>t;
    for (i=1;i<=t;i++)
    {
        f>>n>>k;
        if (mat[k][0]>n)
         g << 0 << "\n";
        else
        { 
        st=0;
        dr=l[k]-1;
        x=0;
        while (st<=dr)
        {
            mij=(st+dr)/2;
           if ( mat[k][mij] <= n ) { st = mij + 1; x = mij; }
           else if (mat[k][mij]>n) dr=mij-1;
        }
         if ( mat[k][x] <= n ) g << mat[k][x] << "\n";
          else g << 0 << "\n";         
        }  
   } 
    f.close();
    g.close();
}