NAIPC 2019

#### Start

2019-03-02 09:00 AKST

## NAIPC 2019

#### End

2019-03-02 14:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1182 days 6:28:59

5:00:00

0:00:00

# Problem DIt's a Mod, Mod, Mod, Mod World

You are given multiple problems with three integers $p$, $q$, and $n$. Find $\sum \limits _{i=1}^ n [(p{\cdot }i) \bmod {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{\le }W{\le }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{\le }p,q,n{\le }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.

Sample Input 1 Sample Output 1
3
2 7 2
1 4 5
3 8 10

6
7
37