#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t,k,n[10001],m[10001];
int i,j,p,o;
int s;

int jc(int x)
{int end=1;
for(o=1;o<=x;o++)
end*=o;
return end;
}
int pd(int i,int j)
{
int c;
c=jc(i)/jc(j)/jc(i-j);
if(c%k==0)return 1;
}
int js(int p)
{s=0;
for(i=1;i<=n[p];i++)
{
for(j=1;j<=m[p];j++)
{
if(pd(i,j)==1)s++;
}

}
cout<<s<<endl;
}
int main ()
{

cin>>t>>k;
for(i=1;i<=t;i++)
cin>>n[i]>>m[i];
for(p=1;p<=t;p++)
{js(p);
}
return 0;

}