#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()

using namespace std;

template<class A> string to_string(A v) {
	bool first = 1;
	string res = "{";
	for (const auto &x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}

void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

ll solve(ll a, ll b, ll c, ll n) {
	if (a >= c || b >= c) {
		ll res = solve(a % c, b % c, c, n);
		res += (a / c) * n * (n + 1) / 2;
		res += (b / c) * (n + 1);
		return res;
	}
	if (a == 0) return 0;
	return ((a * n + b) / c) * n - solve(c, c - b - 1, a, (a * n + b) / c - 1);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int cas; cin >> cas; while (cas--) {
		ll p, q, n; cin >> p >> q >> n;
		p %= q;
		ll ans = p * n * (n + 1) / 2 - q * solve(p, 0, q, n);
		printf("%lld\n", ans);
	}
	return 0;
}