题目描述

给定多个测试用例，每个测试用例包含三个整数 $p$、$q$ 和 $n$。求 $\sum_{i=1}^{n} [(p \cdot i) \bmod q]$，即 $p$ 的前 $n$ 个倍数分别对 $q$ 取模后的和。注意，总和不需要取模。

输入格式

每个输入的第一行包含一个整数 $W$（$1 \leq W \leq 10^5$），表示你需要解决的测试用例个数。

接下来的 $W$ 行，每行包含三个空格分隔的整数 $p$、$q$ 和 $n$（$1 \leq p, q, n \leq 10^6$），即上述问题中的参数。

输出格式

输出 $W$ 行，每行一个整数，表示对应测试用例的答案，按输入顺序输出。

3
2 7 2
1 4 5
3 8 10

6
7
37

提示

翻译由 DeepSeek V3.2 完成