x+y+z<=k
x+y+z+d=k
就等价于把k个东西放到4个框里，隔板法
因为可以为空所以先补4个空格，共k-1+4个空格，取3个隔板，分4份
即c（3，k-1+4）

c（3，k+3）=（k+1）*（k+2）*（k+3）/6%m
（k+1）*（k+2）/6*（k+3）会爆longlong，所以%m要放到（k+1）*（k+2）%m
（k+1）*（k+2）*（k+3）/6%m 因为（k+1）*（k+2）*（k+3）%6=0
=（k+1）*（k+2）*（k+3）%（m*6）/6
=（k+1）*（k+2）%（m*6）*（k+3）%（m*6）/6 
#include <bits/stdc++.h>

using namespace std;

long long t,k,m;

int main(int argc, char** argv) {
	cin>>t;
	while(t--){
		scanf("%lld%lld",&k,&m);
		long long  ans=1LL*(k+3)*(k+2)%(m*6);
		ans=ans*(k+1)%(6*m)/6;
		cout<<ans<<endl;
	}
	return 0;
}