#include <bits/stdc++.h>
#define ff first
#define ss second
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int B = 1000;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	
	int T; cin >> T;
	while(T--)
	{
		int p, q, n; cin >> p >> q >> n;
		long long ans = 0;
		int t = n / B;
		for(int i = t * B; i <= n; ++i) ans += 1ll * i * p % q;
		if(t)
		{
			int A[B];
			long long s = 0;
			for(int i = 0; i < B; ++i) A[i] = 1ll * i * p % q, s += A[i];
			sort(A, A + B);

			long long l = 0;
			int K[t];
			for(int i = 0; i < t; ++i) K[i] = 1ll * B * i * p % q, l += K[i];
			sort(K, K + t);

			long long m = 0;
			int pt = B;
			for(auto k : K)
			{
				while(pt > 0 && A[pt - 1] >= q - k) --pt;
				m += B - pt;
			}

			ans += s * t + B * l - m * q;
		}
		cout << ans << '\n';
	}
}