#include<iostream>
#define MOD 2e+7
using namespace std;
int main()
{
long long int q,a,b,p;
cin >> q;
while(q--){
cin >> a >> b >> p;
long long int index = b,base = a,ans = 0;
while(index){
if(index % 2 != 0)
ans = (ans + base) % p;
base = base + base;
base = base % p;
index /= 2;
}
cout << ans << endl;
}
}