#include<stdio.h>
#include<stdlib.h>

int compare(const void *a ,const void *b)
{
return *(int*)a-*(int*)b;
}
int main(void)
{
long int e[10000],d[10000];
long int r,s,a,b,c,f,g,h,i=0,j,k,l,x,y,z;
scanf("%ld",&a);
while(a--)
{
i=0;
scanf("%ld %ld",&b,&c);
if(c==1)
{
printf("%ld\n",c);
continue;
}
d[i]=1;
i++;
for(f=2;f<=b;f++)
{
if(f%2==0&&f!=2||f%3==0&&f!=3||f%5==0&&f!=5||f%7==0&&f!=7)
continue;
    g=f;
    k=0;
    for(h=1;h<=g;h++)
    {
      if(g%h==0)
      k++;
    }
    if(k==2)
    {
      d[i]=f;
      i++;
    }
}
l=0;
for(j=0;j<i;j++)
{
for(s=0;s<i;s++)
{
f=d[j]*d[j]+d[s]*d[s];
    g=f;
    k=0;
    for(h=1;h<=g;h++)
    {
      if(g%h==0)
      k++;
    }
    if(k==2)
    {
      e[l]=f;
      l++;
    }
}
}
qsort(e,l,sizeof(int),compare);
z=e[l-1];
if(c==2)
{
z=z/2+1;
printf("%ld\n",z);
continue;
}
if(c==3)
{
r=0;
x=z/3;
for(i=x;i>=0;i--)
{
 y=z-3*i;
 r+=y/2+1;

}
z=r;
printf("%ld\n",z);
continue;
}
}
return 0;
}