#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
    int T; cin >> T;
    string N_str;
    ll N_mod, M, ans;

    for (int t = 1; t <= T; t++){
        cin >> N_str >> M;

        N_mod = 0;
        for (auto n: N_str){
            N_mod = (10 * N_mod + (n - '0')) % (2 * M);
        }

        ans = (N_mod * (N_mod + 1) % (2 * M)) / 2;
        cout << ans << endl;
    }
    return 0;
}