#include <bits/stdc++.h>

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";
    }
}