// Arup Guha
// 11/27/2020
// Solution to 2019 NAIPC Problem: It's a Mod, Mod, Mod World

import java.util.*;
import java.io.*;

public class modmodmod {
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		int nC = Integer.parseInt(stdin.readLine());
		
		// Process all cases.
		StringBuffer sb = new StringBuffer();
		for (int loop=0; loop<nC; loop++) {
			StringTokenizer tok = new StringTokenizer(stdin.readLine());
			int p = Integer.parseInt(tok.nextToken());
			int q = Integer.parseInt(tok.nextToken());
			int n = Integer.parseInt(tok.nextToken());
			sb.append(f(n, p, q)+"\n");
		}
		
		// Just output once.
		System.out.print(sb);
	}
	
	// Get it started!
	public static long f(int n, int p, int q) {
		return ((long)p)*n*(n+1)/2 - q*g(n,p,q);
	}
	
	// This function calculates the sum of floor(pi/q) from i=1 to n,
	// this is what we subtract out from the "whole" sum in f.
	public static long g(int n, int p, int q) {
	
		// I hope this is enough for base cases!
		if (q == 0) return 0;
		if (q == 1) return ((long)p)*n*(n+1)/2;
	
		// The sum is a bit easier here as we can cancel with p and q.
		int div = gcd(p, q);
		if (div != 1) return g(n, p/div, q/div);
		
		// We can split the sum and take out an integer portion of it.
		if (p > q) return ((long)(p/q))*n*(n+1)/2 + g(n, p%q, q);
		
		// # of terms in new sum.
		long terms = ((long)p)*n/q;
		
		// Kind of a crazy formula, comes from looking at the some in a weird way.
		// Count how many terms are >= 1, how many >= 2, etc. and add up these numbers
		// instead. Then, you work with that new expression and eventually you get this
		// when you substitute ceilings for floors and compensate for the terms where the
		// ceiling and floors are unequal by 1.		
		return ((long)(n+1))*terms - g( (int)terms, q, p) - terms + terms/p;
	}
	
	public static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a%b);
	}
	
}