#include<stdio.h>

const int MAX=1000000;

 int div[1000000],T,k,N;

long long int i,j,mark,v[7]={2,6,30,210,2310,30030,510510};
int main()
{


FILE*in=fopen("divprim.in","r");
FILE*out=fopen("divprim.out","w");


fscanf(in,"%d",&T);
div[1]=1;
for(i=2;i<=MAX/2;i++)
 div[2*i]=1;
for(i=3;i<=MAX;i=i+2)
 {
  if(div[i]==0)
   {
    for(j=2;j<=MAX/i;j++)
     div[j*i]+=1;
   }
 }

for(i=1;i<=T;i++)
{
 fscanf(in,"%d %d",&N,&k);
 if(k==0) fprintf(out,"1\n");
  else
 {
  if(N<v[k]) fprintf(out,"0\n");
  else
  {
  mark=N;
  while(mark>=1)
  {
   if(div[mark]==k||k==1&&div[mark]==0) break;
   mark--;
  }
   fprintf(out,"%d\n",div[mark]);
  }
 }
 }
fcloseall();
return 0;
}