Problem Description
You are given multiple problems with three integers p, q, and n. Find ∑ni=1[(pi)mod. That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus.
Input
Each input will begin with a line with a single integer W (1 \leq W \leq 10^5), which is the number of cases you must solve.
Each of the next W lines will contain three space-separated integers p, q and n (1\leq p, q, n \leq 10^6), which are the parameters of the problem as described above.
Output
Output W lines, each with the answer for a given instance of the problem, in the order that they appear in the input.
Sample
Sample Input
3
2 7 2
1 4 5
3 8 10
Sample Output
6
7
37