#include <bits/stdc++.h>
using namespace std;
string sum_uno(string n) {
	int tmp = 1;
	for (int i = (int)n.length() - 1; i >= 0; --i) {
		if (tmp == 0) break;
		if (n[i] == '9') {
			n[i] = '0';
		}
		else {
			n[i] += 1;
			tmp = 0;
		}
	}
	if (tmp == 1) {
		n = '1' + n;
	}
	return n;
}
string div_2(string n) {
	string ans;
	int tmp = 0;
	for (char dig : n) {
		int v = (dig - '0') + tmp * 10;
		ans += (v / 2) + '0';
		tmp = v % 2;
	}
	if (ans[0] == '0'){
		ans = ans.substr(1);
	}
	return ans;
}

void solve() {
	string number;
	int m;
	cin >> number >> m;
	
	int n = 0, q = 0;
	int k = (int)number.size();
	if ((number[k - 1] - '0') % 2 != 0) {
		string p = sum_uno(number);
		p = div_2(p);
		int residuo = 1;
		for (int i = (int)number.size() - 1; i >= 0; --i) {
			n = n + (residuo * (number[i] - '0')) % m;
			residuo = residuo * 10 % m;
		}
		int res = 1;
		for (int i = (int)p.size() - 1; i >= 0; --i) {
			q = q + (res * (p[i] - '0')) % m;
			res = res * 10 % m;
		}
	}
	else {
		string p = sum_uno(number);
		number = div_2(number);
		int residuo = 1;
		for (int i = (int)number.size() - 1; i >= 0; --i) {
			n = n + (residuo * (number[i] - '0')) % m;
			residuo = residuo * 10 % m;
		}
		int res = 1;
		for (int i = (int)p.size() - 1; i >= 0; --i) {
			q = q + (res * (p[i] - '0')) % m;
			res = res * 10 % m;
		}
	}
	long long result = 1ll * n * q % m;
	cout << result << "\n";
}

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