#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e3 + 10;
int C[N][N];
int n, m;
int main()
{
    int t, k;
    cin >> t >> k;
    
    while (t --)
    {
        cin >> n >> m;
        int cnt=0;
        for (int i=0; i <= n; i ++)
        {
            C[i][0] = C[i][i] = 1;
            for (int j=1; j <= min(i, m); j ++)
            {
                C[i][j] = (C[i-1][j] + C[i-1][j-1]) % k;
                if (C[i][j] == 0)
                    cnt ++;
            }
        }
        cout << cnt << endl;
    }
    
    return 0;
}