QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB
[-1]

# 3004. It's a Mod, Mod, Mod, Mod World

Statistics

Problem Description

You are given multiple problems with three integers p, q, and n. Find ni=1[(pi)mod. 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 \leq W \leq 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\leq p, q, n \leq 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

Sample Input

3
2 7 2
1 4 5
3 8 10

Sample Output

6
7
37