#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int n,m,k;

int f[maxn][maxn];

int sum[maxn][maxn];

int main(){int T;

    scanf("%d%d",&T,&k);

    f[][]=;

    f[][]=f[][]=;

    for(int i=;i<=;i++)f[i][]=;

    for(int i=;i<=;i++){

        for(int j=;j<=i;j++){

            f[i][j]=(f[i-][j]+f[i-][j-])%k;

            sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-];

            if(f[i][j]==)sum[i][j]++;

        }

        sum[i][i+]=sum[i][i];

    }

    for(int pp=;pp<=T;pp++){

        scanf("%d%d",&n,&m);

        m=min(m,n);

        printf("%d\n",sum[n][m]);

    }

}