시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB70729719844.098%

문제

You are given multiple problems with three integers p, q, and n. Find \(\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)}\). That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus.

입력

Each input will begin with a line with a single integer W (1 ≤ W ≤ 105), 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 ≤ p, q, n ≤ 106), which are the parameters of the problem as described above.

출력

Output W lines, each with the answer for a given instance of the problem, in the order that they appear in the input.

예제 입력 1

3
2 7 2
1 4 5
3 8 10

예제 출력 1

6
7
37