#include <bits/stdc++.h>
using namespace std;

const int maxn = 2016;
const int maxt = 10002;

int c[maxn][maxn], k, t, sum[maxn][maxn], a[maxt], b[maxt], ma, mb;

void init() {
    for (int i = 0; i <= ma; i++) c[i][i] = c[i][0] = 1;
    for (int i = 1; i <= ma; i++)
        for (int j = 1; j < i; j++)
            (c[i][j] = c[i - 1][j - 1] % k + c[i - 1][j] % k) %= k;
}

int main() { 
    freopen("problem.in", "r", stdin);
    freopen("problem.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin >> t >> k;
    for (int i = 1; i <= t; i++) {
        cin >> a[i] >> b[i];
        ma = max(a[i], ma);
        mb = max(b[i], mb);
    }
    init();
    for (int i = 0; i <= ma; i++) {
        for (int j = 0; j <= i; j++)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + !(c[i][j]);
        for (int j = i + 1; j <= mb; j++)
            sum[i][j] = sum[i][j - 1];
    }
    for (int i = 1; i <= t; i++)
        cout << sum[a[i]][b[i]] << endl;
}
// 此致我的NOIP2016