include

using namespace std; const int MAX_N = 2005; int c[MAX_N][MAX_N];
int pre[MAX_N][MAX_N]; int sum[MAX_N][MAX_N]; int main() {

int t, k;
cin >> t >> k;
for (int i = 0; i < MAX_N; ++i) {
    for (int j = 0; j < MAX_N; ++j) {
        c[i][j] = 0;
        pre[i][j] = 0;
        sum[i][j] = 0;
    }
}
for (int i = 0; i < MAX_N; ++i) {
    c[i][0] = 1 % k;  
    if (i > 0) 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;
    }
}
for (int i = 0; i < MAX_N; ++i) {
    int cnt = 0;
    for (int j = 0; j <= i; ++j) {
        if (c[i][j] == 0) cnt++;
        pre[i][j] = cnt;
    }
    for (int j = i+1; j < MAX_N; ++j) {
        pre[i][j] = pre[i][i];
    }
}
for (int j = 0; j < MAX_N; ++j) {
    int total = 0;
    for (int i = 0; i < MAX_N; ++i) {
        total += pre[i][j];
        sum[i][j] = total;
    }
}
while (t--) {
    int n, m;
    cin >> n >> m;
    int limit = (n < m) ? n : m;
    cout << sum[n][limit] << endl;
}

return 0;

}