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

void solve() {
	string number;
	int m;
	cin >> number >> m;
	
	int n = 0;
	int residuo = 1;
	for (int i = (int)number.size() - 1; i >= 0; --i) {
		n = n + (residuo * (number[i] - '0')) % m;
		residuo = residuo * 10 % m;
	}
	long long result = (1ll * n * (n + 1))/ 2;
	cout << result % m << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int test = 1;
	cin >> test;
	while (test--) {
		solve();
	}
	return 0;
}