#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int f[][];

int n,m,q,t;

int ans[][];

int main(){

    scanf("%d%d",&t,&q);

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

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

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

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

        {

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

            f[i][j]%=q;

            if(f[i][j]==)ans[i][j]=ans[i][j-]+; else ans[i][j]=ans[i][j-];

        }

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

    {

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

        int tot=;

        for(int j=;j<=n+;j++)

        tot+=ans[j][min(m+,j)];

        printf("%d\n",tot);

    }

    return ;

}