CHIA DU TICH HAI SO

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long ChiaDuTichHaiSo(long long a,long long b,long long mod){
    long long res = 0; // biến kết quả ban đầu = 0
    a %= mod; // Nếu a lớn hơn hoặc bằng mod thì chia dư a cho mod để được một số nhỏ hơn mod
    while (b!=0){
        if (b % 2 == 1){ // Nếu b lẻ
            res = (res + a) % mod; // Cộng a vào kết quả, sau đó chia cho mod
        }
        // Nếu b chẵn
        a = (2 * a) % mod; // Chia dư 2*a cho mod để đảm bảo không bị tràn số
        b = b/2; // Chia b cho 2
    }
    return res;
}

int main(){
    int t;
    cin >> t;
    while (t--) {
        long long a, b, m;
        cin >> a >> b >> m;
        cout << ChiaDuTichHaiSo(a, b, m) << endl;
    }
    return 0;
}