#include <iostream>
#include <algorithm>
using namespace std;

long long n, m, ret, cc, i, j, retb, q, add, mpref, al, ar, last_r, last_ar;
int tn, precalc[1000000 + 5];
bool act;

void die () {
	cout << "Fail" << endl;
	exit(0);
}

inline long long prefix (long long n) {
	if (n > m) {
		q = n / m;
		add = (q % m * mpref) % m;
		n %= m;		
	} else add = 0;
	if (act) return add + precalc[n];
	if (n == 0) return add;
	long long t1 = n * (1 + n) * (1 + 2 * n);
//	long long t2 = 1 + n;
//	long long t3 = 1 + 2 * n;
	long long t2 = -1 + 3 * n + 3 * n * n;
	if (t1 % 2 == 0) t1 /= 2; else t2 /= 2;
//			if (t3 % 2 == 0) t3 /= 2; else
//				if (t4 % 2 == 0) t4 /= 2; else die();
	if (t1 % 3 == 0) t1 /= 3; else t2 /= 3;
//			if (t3 % 3 == 0) t3 /= 3; else
//				if (t4 % 3 == 0) t4 /= 3; else die();
	if (t1 % 5 == 0) t1 /= 5; else t2 /= 5;
//			if (t3 % 5 == 0) t3 /= 5; else
//				if (t4 % 5 == 0) t4 /= 5; else die();	
	t1 %= m, t2 %= m;
	return (add + t1 * t2) % m;
}

inline long long lalka (long long l, long long r) {
	
	ar = prefix(r);
	if (last_r == l - 1) al = last_ar; else al = prefix(l - 1);
	
	last_r = r;
	last_ar = ar;
	
	return (ar - al + m) % m;
}

int main (int argc, char * const argv[]) {
	ios_base::sync_with_stdio(0);
	cin >> tn;
	while (tn--) {
		cin >> n >> m;
		
		if (n > 1000000) act = 1; else act = 0;
				
		last_r = -1;

		if (act) {
		
			for(i = 1; i <= m; i++) precalc[i] = (precalc[i - 1] + 1LL * i * i % m * i % m * i % m) % m;
			mpref = precalc[m];
			
		} else mpref = prefix(m);
		
		i = 1; ret = 0;
		while (i <= n) {
			cc = n / i;
			j = n / cc; 
			if (i <= j - 1) {
				ret = (ret + lalka(i, j - 1) % m * (cc % m)) % m;
//				cout << i << " " << j - 1 << " " << cc << endl;
			}
			i = j;
			if(n / i == cc) {
				long long im = i % m;
				ret = (ret + (im * im * im % m * im) % m * (cc % m)) % m;
//				cout << i << " " << i << " " << cc << endl;
				++i;
			}
		}
		if (ret < 0) cerr << n << " " << m << endl;
		cout << ret << endl;
	}	
    return 0;
}