#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll c[2010][2010],h[2010],f[2010][2010];
int n,m,k;
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘);
    do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘);
    return f*x;
}
int main(){
    int T=read();k=read();c[0][0]=1;
    for(int i=1;i<=2001;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
            if(!c[i][j])h[i]++;
            f[i][j]=f[i-1][j]+h[i];
            if(i==j)f[i][j]=f[i-1][j-1]+h[i];
        }
    }
    while(T--){
        n=read();m=read();
        if(m>n)m=n;
        printf("%lld\n",f[n][m]);
    }
}