#include <iostream>
#include <string>

using namespace std;
using ll = long long;

void solve (string N, int M) {
    // 拡張MODのやつ
    const ll ext_mod = 2 * M;

    // 変換
    ll radix = 1;
    ll n = 0;
    for (int i = N.size()-1; 0 <= i; i--) {
        n += ((N[i] - '0') * radix) % ext_mod;
        n %= ext_mod;

        radix *= 10;
        radix %= ext_mod;
    }

    ll ans = n * (n+1) % ext_mod;
    ans /= 2;

    cout << ans << "\n";
}

int main () {
    int T; cin >> T;
    for (int t = 0; t < T; t++) {
        string N;
        int M;
        cin >> N >> M;

        solve(N, M);
    }
}