#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);
    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%=q;
    ans+=(1+n)*n/2*p;
    // n++;
    // cout<<base<<endl;
    if(n>fjd*(cnt+1)){
        // ll val=n-fjd;    
        ans-=cal1(n-fjd*(cnt+1));
    }
    n=min(fjd,n);
    cnt++;
    fjd=0;
    ans-=cal1(n);
    printf("%lld\n",ans);
}
//0 3 6
//1 4 7
//2 5 
//0 2 4 6


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