#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int _; cin >> _;
	while (_--) {
		string s; cin >> s;
		i64 m; cin >> m;
		i64 res = 0;
		for (auto &ch : s)
			res = (res * 10 + ch - '0') % (m * 2);
		res = (res + 1) * res / 2;
		cout << res % m << '\n';
	}
	return 0;
}