#include <fstream>
using namespace std;

int st,dr,mij,x=0,i,j,t,k=0,n,mat[8][1000005],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];
        
      } 
    for (i=2;i<= 1000000;i++)
     switch(v[i])
      { 
        case 0: mat[0][l[0]++]=i;
             break;                         
        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;
        st=0;
        dr=l[k]-1;
        x=0;
        while  ( (st<=dr) && (!x) )
        {
            mij=(st+dr)/2;
            if ( mat[k][mij] <= n ) { st = mij + 1; x = mij; }
           else if (mat[k][mij]>n) dr=mij-1;
        }
        if (x>0)
          g<<mat[k][mij]<<"\n";
        else  
          g<<"0"<<"\n";
   } 
    f.close();
    g.close();
}