import java.util.*;

/*
 * Problem: Mod Mod Mod (NAIPC19)
 * Author: Alex Coleman
 * Complexity: O(c*min(log(p),log(q)))
 * 
 * Instead of solving for the sums of mods, we solve for
 * f(p,q,n) = sum of floor((p*i)/q) for i=0..n, and find a recurrence
 * by instead summing across the value of floor((p*i)/q), and taking i*frequency(i)
 * s.t. f(p,q,n) = O(1) formula in terms of f(q,p,n)
 * Additionally, if p > q, we can reduce p to p%q with O(1) work
 * Thus our complexity is the same as euclidean, log(p) or log(q)
 * Given f(p,q,n), the original problem can be solved with a simple O(1) formula
 */
public class ModModMod_arc {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int c = in.nextInt();
		while (c --> 0) {
			long p = in.nextInt(), q = in.nextInt(), n = in.nextInt();
			long gcd = gcd(p, q);
			System.out.println(n*(n+1)/2*p - q*f(p/gcd, q/gcd, n));
		}
	}
	static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a%b);
	}
	static long f(long p, long q, long n) {
		long ans = n*(n+1)/2 * (p/q);
		p %= q;
		if (p != 0) {
			long N = (p*n)/q;
			ans += n * N - f(q, p, N) + N/p;
		}
		return ans;
	}
}