#include<bits/stdc++.h>
using namespace std;
int t, k, n, m, a[2010][2010] = {0}, num[2010][2010] = {0};
int main() {
    freopen("problem.in", "r", stdin);
    freopen("problem.out", "w", stdout);
    cin >> t >> k;
    a[0][0] = 1;
    for(int i = 1; i <= 2000; i ++) {
    	a[i][i] = 1;
    	a[i][0] = 1;
    	for(int j = 1; j <= min(i, 2000); j ++) {
    		a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
    		a[i][j] %= k;
    		if(a[i][j] == 0) {
    			num[i][j] = num[i][j - 1] + 1;
			}
			else {
				num[i][j] = num[i][j - 1];
			}
		}
	}
    for(int tt = 1; tt <= t; tt ++) {
    	cin >> n >> m;
    	int ans = 0;
    	for(int i = 1; i <= n ; i ++) {
    		ans += num[i][min(i, m)];
		}
		cout << ans << endl;
	}
    return 0;
}