Problem Description
You are given multiple problems with three integers $p$, $q$, and $n$. Find $\sum^n_{i=1}[(pi) \bmod q]$. 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 10Sample Output
6
7
37