#include using namespace std; void fast_io() { ios::sync_with_stdio(false); std::cin.tie(nullptr); } int main() { fast_io(); int t; cin >> t; for (; t--;) { string n; long long m; cin >> n >> m; long long ans = 0; for (char c : n) { ans = (ans * 10 + (c - '0')) % m; } ans = ans * (ans + 1) / 2 % m; cout << ans << "\n"; } }