#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll Solve(int p,int q,int n){
	if(p>=q){
		return Solve(p%q,q,n);
	}
	if(p==0)return 0;
	if(q%p==0){
		int t=q/p;
		if(n>t){
			return Solve(p,q,t)*(n/t)+Solve(p,q,n%t);
		}
		int blk=q/p;
		int blks=n/blk;
		ll ans=(ll)n*(n-1)/2*p;
		ans-=(ll)blks*(blks-1)/2*q*blk;
		ans-=(ll)blks*(n-blks*blk)*q;
		return ans;
	}
	int n1=(ll)p*(n-1)/q+1;
	ll tmp=Solve(q,p,n1);
	ll sum=(ll)n1*(n1-1)/2*q;
	sum-=tmp;
	ll need=p/__gcd(p,q);
	int dv=(n1+need-1)/need;
	sum+=(ll)p*(n1-dv);
	sum/=p;
	sum=(ll)n*(n1-1)-sum;
	ll ans=(ll)n*(n-1)/2*p;
	ans-=sum*q;
	return ans;
}

int main(){
	int t;
	scanf("%i",&t);
	while(t--){
		int p,q,n;
		scanf("%i %i %i",&p,&q,&n);
		ll ans=Solve(p,q,n+1);
		printf("%lld\n",ans);
	}
	return 0;
}