It's a Mod, Mod, Mod, Mod World

Time limit5sMemory limit512 MB

Summary

Given p, q, n, compute the sum of (p*i mod q) for i from 1 to n, for up to 100000 queries with values up to 10^6.

Level: Hard8 of 10
Topics: Math, Number theory, Divide and conquer, Binary search
Solved: No attempts yet

Problem

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.

Input

Each input will begin with a line with a single integer W (1 ≤ W ≤ 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 ≤ p, q, n ≤ 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.

Examples1

Example 1
Input
```
3
2 7 2
1 4 5
3 8 10
```
Expected output
```
6
7
37
```