#include <iostream>
using namespace std;

const int MAX = 2005;
int c[MAX][MAX];    // 组合数模k的结果
int row[MAX][MAX];  // 每行的前缀和（满足条件的数量）
int pre[MAX][MAX];  // 答案前缀和：pre[n][m] 对应查询n,m的答案

int main() {
    // 文件IO（题目要求problem.in/problem.out）
    freopen("problem.in", "r", stdin);
    freopen("problem.out", "w", stdout);

    int t, k;
    cin >> t >> k;

    // 1. 递推预处理组合数模k
    c[0][0] = 1 % k;
    for (int i = 1; i < MAX; ++i) {
        c[i][0] = 1 % k;
        c[i][i] = 1 % k;
        for (int j = 1; j < i; ++j) {
            c[i][j] = (c[i-1][j-1] + c[i-1][j]) % k;
        }
    }

    // 2. 预处理每行的前缀和（统计该行前j列中模k为0的数量）
    for (int i = 0; i < MAX; ++i) {
        row[i][0] = (c[i][0] == 0) ? 1 : 0;
        for (int j = 1; j < MAX; ++j) {
            if (j <= i) {
                row[i][j] = row[i][j-1] + (c[i][j] == 0);
            } else {
                // j超过i时，组合数无意义，取该行最大值（j=i时的和）
                row[i][j] = row[i][i];
            }
        }
    }

    // 3. 预处理二维答案前缀和
    for (int m = 0; m < MAX; ++m) {
        pre[0][m] = row[0][m];
    }
    for (int n = 1; n < MAX; ++n) {
        for (int m = 0; m < MAX; ++m) {
            pre[n][m] = pre[n-1][m] + row[n][m];
        }
    }

    // 4. 处理t组查询
    while (t--) {
        int n, m;
        cin >> n >> m;
        cout << pre[n][m] << endl;
    }

    return 0;
}