시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 11 10 4 100.000%

문제

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