tj

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

int t;                  // 测试用例数量
int k;                  // 模数
int a[2005][2005];      // 存储组合数模k的结果
int f[2005][2005];      // 前缀和数组，记录满足条件的组合数数量
int n, m;               // 每次查询的参数

int main()
{
    // 输入测试用例数量和模数
    cin >> t >> k;

    // 初始化组合数数组（杨辉三角）
    a[1][1] = 1;
    for (int i = 1; i <= 2000; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            // 边界条件：第一列和最后一列都为1
            if (j == 1 || j == i)
            {
                a[i][j] = 1;
            }
            else
            {
                // 递推计算组合数并取模
                a[i][j] = (a[i - 1][j - 1] + a[i - 1][j]) % k;
            }
        }
    }

    // 初始化前缀和数组的第一列
    for (int i = 1; i <= 2000; i++)
    {
        f[i][1] = (a[i][1] == 0);
    }

    // 计算前缀和数组
    for (int i = 1; i <= 2000; i++)
    {
        for (int j = 2; j <= i; j++)
        {
            // 分情况计算前缀和
            if (i - 1 < j)
            {
                f[i][j] = f[i - 1][i - 1] + f[i][j - 1] - f[i - 1][j - 1];
            }
            else
            {
                f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
            }

            // 如果当前组合数模k等于0，则计数加1
            f[i][j] += (a[i][j] == 0);
        }
    }

    // 处理每个查询
    while (t--)
    {
        cin >> n >> m;
        // 确保m不超过n
        m = min(n, m);
        // 输出结果（注意索引偏移）
        cout << f[n + 1][m + 1] << endl;
    }

    return 0;
}