#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll Fab(int x)     //求阶乘
{
    if(x<=1)
        return 1;
    return x*Fab(x-1);
}

int main()
{
    int t,k;
    cin>>t>>k;
    while(t--)
    {
        int n,m,cnt=0;
        cin>>n>>m;
        for(int i=0;i<=n;i++)
        {
            int temp=min(i,m);
            for(int j=0;j<=temp;j++)
            {
                if(j!=0&&i!=j&&((Fab(i)/(Fab(j)*Fab(i-j)))%k==0))
                    cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}