It’s a Mod, Mod, Mod, Mod World

W개의 입력마다 p의 처음 n개 배수를 q로 나눈 나머지의 합을 구한다.

어려움8수학정수론분할 정복아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제 설명

예제1

문제

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.