#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define il inline

#define Rg register

#define go(i,a,b) for(Rg int i=a;i<=b;++i)

#define yes(i,a,b) for(Rg int i=a;i>=b;--i)

#define mem(a,b) memset(a,b,sizeof(a))

#define ll long long

#define db double

#define inf 2147483647

using namespace std;

il int read()

{

    Rg int x=,y=;char c=getchar();

    while(c<''||c>''){if(c=='-')y=-;c=getchar();}

    while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}

    return x*y;

}

const int N=;

int T,k,n,m,c[N][N];

ll s[N][N];

il void init()

{

    c[][]=;

    go(i,,)c[i][]=;

    go(i,,)

        go(j,,i)

    {

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

        if(!c[i][j])s[i][j]=;

    }

    go(i,,)

    {

        go(j,,i)s[i][j]+=s[i-][j]+s[i][j-]-s[i-][j-];

        s[i][i+]=s[i][i];

    }

}

int main()

{

    T=read();k=read();init();

    while(T--)

    {

        n=read(),m=read();

        if(m>n)m=n;

        printf("%lld\n",s[n][m]);

    }

    return ;

}