题目描述

Monocarp 经营着一家公司。考虑到他公司在接下来的 $k$ 个月内的工作情况： 在第 $1$ 个月，除了 Monocarp 本人之外，公司里共有 $x$ 名员工，同时有 $y$ 个项目需要完成。在接下来的每一个月中，员工的数量和项目的数量都会各自增加 $1$。

换句话说，在第 $i$ 个月（$0 \le i < k$，下标从 $0$ 开始表示第 $i+1$ 个月），公司里会有 $x+i$ 名员工，并需要完成 $y+i$ 个项目。

在每个月里，Monocarp 会把项目分配给这些员工。每名员工必须被分配到相同数量的项目，并且每个项目最多只能被分配给一名员工。所有未被分配出去的项目都由 Monocarp 自己来完成。他总是会选择一种分配方案，使得他自己完成的项目数量尽可能少。

具体来说，如果在某个月有 $a$ 名员工和 $b$ 个项目，那么 Monocarp 会给每名员工分配恰好 $\lfloor \frac{b}{a} \rfloor$ 个项目，而他自己则会完成 $b \bmod a$ 个项目。

请计算在接下来的 $k$ 个月内，Monocarp 自己总共需要完成多少个项目。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例，仅包含一行，有三个整数 $x, y, k$（$1 \le x \le y \le 10^6$；$1 \le k \le 10^{12}$）。

输出格式

对于每个测试用例，输出一行一个整数，表示在接下来的 $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

说明

样例解释

• 在第一个测试用例中，仅有的一名员工完成了仅有的一个项目，因此 Monocarp 不需要完成任何项目，输出 $0$。
• 在第二个测试用例中： 第 $1$ 个月，$10$ 个项目分配给 $3$ 名员工：每人分配 $3$ 个项目，Monocarp 完成 $1$ 个项目（$10 \bmod 3 = 1$）。 第 $2$ 个月，$11$ 个项目分配给 $4$ 名员工：每人分配 $2$ 个项目，Monocarp 完成 $3$ 个项目（$11 \bmod 4 = 3$）。 答案是 $1 + 3 = 4$。
• 在第三个测试用例中，在这 $6$ 个月中，Monocarp 每个月完成的项目数量分别为 $2, 1, 0, 5, 5, 5$。它们的总和为 $2+1+0+5+5+5=18$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $1 \le x \le y \le 10^6$ 且 $1 \le k \le 10^{12}$。
• 保证所有测试用例的 $y$ 之和不超过 $10^6$。
• 保证所有的输入数值均为整数。