#include <cstdlib>
#include <iostream>
#include <fstream>
#define NM 1000001
FILE *in=fopen("divprim.in","r");
FILE *out=fopen("divprim.out","w");
char p[NM];
int m[8][NM];
void ndiv(int (&m)[8][NM])
{
     int i,j;
     for(i=1;i<=7;i++)
     {
         m[i][1]=0;
         for(j=2;j<NM;j++)
             if(p[j]==i) m[i][j]=j; 
             else m[i][j]=m[i][j-1];
     }
}
void sieve(char (&p)[NM])
{
    int i,j;
    for(i=2;i<NM;i++)
        if(!p[i])
        {
            p[i]++;
            for(j=2;j*i<NM;j++)
                p[i*j]++;
        }
}
int main()
{
    int t,n,k,i;
    sieve(p);
    ndiv(m);
    fscanf(in,"%d",&t);
    for(i=1;i<=t;i++)
    {
        fscanf(in,"%d%d",&n,&k);
        fprintf(out,"%d\n",m[k][n]);
    }
    fclose(in); fclose(out);
    return 0;
}