16998번 - It’s a Mod, Mod, Mod, Mod World 다국어

문제

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 ≤ 10⁵), 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 ≤ 10⁶), 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.

제한

힌트