问题描述

Monocarp 经营着一家公司。接下来有 $k$ 个月：第 $i$ 个月（从 $0$ 开始）有 $x+i$ 名员工，需要完成 $y+i$ 个项目。

每个月中，每名员工必须分到相同数量的项目，每个项目最多分给一名员工。无法分配给员工的项目由 Monocarp 自己完成，并且他会尽量让这个数量最少。

当某个月有 $a$ 名员工和 $b$ 个项目时，每名员工分到 $\left\lfloor\frac{b}{a}\right\rfloor$ 个项目，Monocarp 完成剩余的 $b\bmod a$ 个项目。

请计算接下来 $k$ 个月中，Monocarp 自己完成的项目总数。

输入格式

第一行输入一个整数 $t$，表示测试用例数量。

接下来 $t$ 行，每行输入三个整数 $x,y,k$，分别表示第一个月的员工数、项目数和总月数。

输出格式

对于每个测试用例，输出一行一个整数，表示 Monocarp 需要自己完成的项目总数。

样例输入 1

7
1 1 1
3 10 2
3 8 6
7 20 1
10 25 100
8 36 17
1 999900 1000000000000

样例输出 1

0
4
18
6
1425
110
999898177699820694

样例解释 1

第二个测试用例中，第一个月 Monocarp 完成 $1$ 个项目，第二个月完成 $3$ 个项目，总数为 $4$。

评测数据规模

对于所有数据，保证：

• $1\leq t\leq10000$；
• $1\leq x\leq y\leq10^6$；
• $1\leq k\leq10^{12}$；
• 每个输入文件中所有测试用例的 $y$ 之和不超过 $10^6$。