#include<bits/stdc++.h>

using namespace std;

#define MAXNM 2010

int i,j,n,m,tc,k;

int s[MAXNM+][MAXNM+],c[MAXNM+][MAXNM+];

int main() {

        cin >> tc >> k;

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

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

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

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

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

                }

        }

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

                for (j = ; j <= MAXNM; j++) {

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

                        if ((!c[i][j]) && (j <= i))

                                s[i][j]++;

                }

        }

        while (tc--) {

                cin >> n >> m;

                cout<< s[n][m] << endl;

        }

        return ;

}