/*
 */
#include<bits/stdc++.h>

#ifdef t9unkubj
#define dbg(x) cout<<__LINE__<<" "<<#x<<":="<<x<<endl;
#else 
#define dbg(x) t9unkubj
#endif

using namespace std;
#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;
int main(){
	int t;
	cin>>t;
	for(int _=0;_<t;_++){
		mp::cpp_int n,m;
		cin>>n>>m;
		cout<<(n*(n+1)/2)%m<<endl;
	}
}