#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int c[maxn][maxn];

int n,k;

int ans[maxn][maxn];

void build()

{

    c[][]=;

    c[][]=c[][]=;

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

    {

        c[i][]=;

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

        {

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

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

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

        }

        ans[i][i+]=ans[i][i];

    }

}

int T,m;

int x;

int main()

{

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

    build();

    while(T--)

    {

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

        x=min(n,m);

        printf("%d\n",ans[n][x]);

    }

    return ;

}