#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;

ll p,q,n;
int a[N],b[N];
char s[N],t[N];
ll dp[N][114];
ll gg,fjd,cnt,tot,base;
ll cal1(ll x){
    ll cc=x/cnt;
    ll mul=cnt*q;
    ll res=(fjd+fjd+cc-1)*cc/2*mul;
    x%=cnt;
    ll ffjd=fjd+cc;
    res+=ffjd*q*x;
    // cout<<"--"<<res<<endl;
    return res;
}


void __(){
    scanf("%lld%lld%lld",&p,&q,&n);
    
    //  n++;
    p%=q;
    if(p==0){
        puts("0");
        return;
    }
    gg=__gcd(p,q);
     fjd=q%p;
    cnt=q/p;
    tot=q/gg;
     base=(q-gg)*(tot)/2;
    ll ans=base*(n/q);
    // ans+=(1+n)*n/2*p;
    n%=tot;
    ll val=0;
    // cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        val+=p;
        if(val>=q) val-=q;
        // cout<<val<<endl;
        ans+=val;
    }
    printf("%lld\n",ans);
}
//3 4 7
//0 3
//2
//1
//7 4 1 8 5 2
//0 3 6
//1 4 7
//2 5 
//0 2 4 6


int main(){
    int _=1;
    cin>>_;
    while(_--){
        __();
    }
}