#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define x first
#define y second
#define eb emplace_back
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define sz(x) (int)(x).size()
#define make_unique(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())

using namespace std;

typedef long long i64;
//typedef __int128 i128;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<i64> vl;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef tuple<int,int,int> iii;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

int readInt() { int a; scanf("%d",&a); return a; }
i64 readLong() { i64 a; scanf("%lld",&a); return a; }
char readChar() { char a; scanf(" %c",&a); return a; }
double readDouble() { double a; scanf(" %lf",&a); return a; }
void readString(char *s) { scanf(" %s",s); }

const int mod = 998244353;
int add(int a, int b) { return ((a+=b)>=mod) ? a-mod:a; }
int mul(int a, int b) { return a*1ll*b%mod; }
int pw(int a, int b) {
	int ans = 1, res = a;
	for(int i = 1; i <= b; i*=2, res=mul(res,res)) {
		if(i&b) {
			ans = mul(ans, res);
		}
	}
	return ans;
}

void solve() {
	int p = readInt();
	int q = readInt();
	int n = readInt();

	p%= q;

	i64 A = p*1ll*n*(n+1)/2;

	if(q <= 1000) {
		i64 sum = 0;
		i64 cur = 0;
		i64 m = 0;
		FOR(i,1,q) {
			cur += p;
			if(cur >= q) {
				m += 1;
				cur -= q;
			}
			sum += m;
			//printf("%d: %lld %lld\n",i,cur,m);
		}

		i64 k = n/q;
		i64 ans = k*sum + m*q*k*(k-1)/2;
		m *= k;

		n %= q;
		assert(cur == 0);

		FOR(i, 1, n) {
			cur += p;
			if(cur >= q) {
				m += 1;
				cur -= q;
			}
			//printf("%d: %lld %lld\n",i,cur,m);
			ans += m;
		}
		printf("%lld\n",A-q*ans);
		return ;
	}

	if(n <= 1000) {
		i64 sum = 0;
		i64 cur = 0;
		i64 m = 0;
		FOR(i,1,n) {
			cur += p;
			if(cur >= q) {
				m += 1;
				cur -= q;
			}
			//printf("%d: %lld\n",i,m);
			sum += m;
		}
		//printf("%lld %lld %lld\n",A,q,sum);
		printf("%lld\n",A-q*sum);
		return ;
	}

	const int B = 1500;
	vector<int> bucket(B);
	//vector<int> prefix(1000);
	i64 ans = 0;
	i64 cur = 0;
	i64 m = 0;
	i64 sum = 0;
	FOR(i,1,B) {
		cur += p;
		if(cur >= q) {
			cur -= q;
			m += 1;
		}
		bucket[i-1] = cur;
		sum += m;
		//ans += m;
	}
	sort(all(bucket));
	//prefix[0] = bucket[0].y;
	//FOR(i,1,999) prefix[i] = prefix[i-1]+bucket[i].y;

	//peek the first few
	
	// loop
	i64 save_cur = cur;
	i64 save_m = m;
	i64 save_sum = sum;
	// reset cur and m
	cur = 0;
	m = 0;
	int i = 0;
	while(n >= B) {
		// cur, m
		// ans
		
		// binary search to update m and ans
		//int idx = upper_bound(all(bucket), pii(cur,1<<30))-bucket.begin()-1;
		int idx = lower_bound(all(bucket), q-cur)-bucket.begin();

		ans += m*B + save_sum + (B-idx);
		//m = p*1ll*(i+B)/q;
		m += save_m;
		cur += save_cur;
		if(cur >= q) {
			cur -= q;
			m += 1;
		}

		n -= B;
		i += B;
	}

	FOR(i,1,n) {
		cur += p;
		if(cur >= q) {
			cur -= q;
			m += 1;
		}
		ans += m;
	}
	printf("%lld\n",A-q*ans);
}

int main() {

	int q = readInt();
	while(q--) {
		solve();
	}
	return 0;
}