#include #include #include #include #include<math.h> using namespace std;

int k,a[5000][5000]; int s[5000][5000];

void st(int k) { a[1][1]=1;//设置初始状态

for(int i=1;i<=2000;i++)
{
    a[i][0]=1;
}

for(int i=2;i<=2000;i++)
{
    for(int j=1;j<=i;j++)
    {
        a[i][j]=(a[i-1][j-1]%k+a[i-1][j]%k)%k;//杨辉三角的求和公式，记得模k，以防爆炸QAQ
    }
}

for(int i=2;i<=2000;i++)
{
    for(int j=1;j<=i;j++)
    {
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//求杨辉三角的每一项符合条件的前缀和
        
        if(a[i][j]==0)
        {
            s[i][j]++;//计算元素本身
        }
    }
    
    s[i][i+1]=s[i][i];//当元素在左右两侧时，该元素的值为1，那么必然没有它自己，同时，他的前缀和的上方元素也是1，也就是说，他的前缀和就是它的前一位元素的前缀和
}

}

int main(void) { int t,k;

cin>>t>>k;

st(k);

while(t--)
{
    int n,m;
    
    cin>>n>>m;
    
    if(m>n)  cout<<s[n][n]<<endl;
    else  cout<<s[n][m]<<endl;
}

return 0;

}