#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e3 + 5;
int f[maxn][maxn],s[maxn][maxn];
int T,k,n = 2e3,m = 2e3;
void init() {
    f[1][0] = f[1][1] = 1;
    for(int i = 2;i <= n;++ i) {
        f[i][0] = 1;
        s[i][0] = s[i - 1][0] + (f[i][0] == 0);
        for(int j = 1;j <= i;++ j) {
            (f[i][j] = f[i - 1][j - 1] + f[i - 1][j]) %= k;
        }
        for(int j = 1;j <= n;++ j)s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (j <= i&&!f[i][j]);
    }
    return ;
}
void work() {
    scanf("%d%d",&n,&m);
    printf("%d\n",s[n][min(n , m)]);
    return ;
}
int main() {
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    scanf("%d%d",&T,&k);
    init();
    for(;T --;)work();
    return 0;
}