#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;
const int MAXN = 2000 + 5;
int t, k;//规模 要求数字 
int n, m;//从n中选m个 
int f[MAXN][MAXN], s[MAXN][MAXN], a[MAXN][MAXN];
void init (int k);
int main()
{
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    cin >> t >> k;
    init(k);//预处理 
    while (t--)
    {
        int cnt = 0;
        cin >> n >> m;
        cout << s[n][m] << endl;
    }
    return 0;
}
void init (int k)
{
    f[0][0] = 1;
    f[1][0] = f[1][1] = 1;
    for (int i = 2; i < MAXN; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            if (i == 0 || i == j) f[i][j] = 1;
            else f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % k;
            if (f[i][j] == 0) a[i][j] = 1;
        }
    }
    for (int i = 1; i < MAXN; ++i)
    {
        for (int j = 1; j < MAXN; ++j)
        {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
}