CF2260B.Monocarp and Projects

Monocarp runs a company. Consider the work of his company over the next $k$ months. In the first month, the company has $x$ employees, not counting Monocarp himself, and $y$ projects need to be completed. In each next month, both the number of employees and the number of projects increase by $1$.

In other words, in month $i$ ($0 \le i \lt k$), the company has $x+i$ employees and needs to complete $y+i$ projects.

In each month, Monocarp distributes the projects among the employees. Each employee must receive the same number of projects, and each project can be assigned to at most one employee. Monocarp completes all unassigned projects himself. He always chooses a distribution that makes him complete as few projects as possible.

In particular, if in some month there are $a$ employees and $b$ projects, then Monocarp assigns exactly $\left\lfloor \frac{b}{a} \right\rfloor$ projects to each employee, and he completes $b \bmod a$ projects himself.

Find the total number of projects that Monocarp will complete himself over the next $k$ months.

Monocarp 经营着一家公司。考虑该公司在未来 $k$ 个月内的情况。在第一个月，公司有 $x$ 名员工（不包括 Monocarp 本人），且需要完成 $y$ 个项目。在接下来的每个月中，员工人数和项目数量均增加 $1$。

换句话说，在第 $i$ 个月（$0 \le i < k$），公司有 $x+i$ 名员工，且需要完成 $y+i$ 个项目。

在每个月中，Monocarp 将项目分配给员工。每名员工必须分配到相同数量的项目，且每个项目最多只能分配给一名员工。所有未被分配的项目均由 Monocarp 自己完成。他总是选择一种分配方式，使得自己完成的项目数尽可能少。

特别地，若某个月有 $a$ 名员工和 $b$ 个项目，则 Monocarp 恰好为每名员工分配 $\left\lfloor \frac{b}{a} \right\rfloor$ 个项目，而他自己完成 $b \bmod a$ 个项目。

求 Monocarp 在未来 $k$ 个月内总共需要自己完成的项目数。

The first line contains an integer $t$ — the number of test cases ($1 \le t \le 10^4$).

Each test case consists of one line containing three integers $x$, $y$, and $k$ ($1 \le x \le y \le 10^6$; $1 \le k \le 10^{12}$).

Additional constraint on the input:

• the sum of $y$ over all test cases does not exceed $10^6$.

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

每个测试用例由一行组成，包含三个整数 $x$、$y$ 和 $k$（$1 \le x \le y \le 10^6$；$1 \le k \le 10^{12}$）。

输入的额外约束条件：

• 所有测试用例的 $y$ 值之和不超过 $10^6$。

For each test case, output one integer — the total number of projects that Monocarp will complete himself over $k$ months.

对于每个测试用例，输出一个整数——Monocarp 在 $k$ 个月内将亲自完成的项目总数。

In the first test case, the only employee completes the only project, so Monocarp is left with no projects.

In the second test case, in the first month, $10$ projects are distributed among $3$ employees: each gets $3$ projects, and Monocarp completes $1$ project. In the second month, $11$ projects are distributed among $4$ employees: each gets $2$ projects, and Monocarp completes $3$ projects. The answer is $1 + 3 = 4$.

In the third test case, the number of projects completed by Monocarp in the six months is $2$, $1$, $0$, $5$, $5$, and $5$, respectively. Their sum is $2 + 1 + 0 + 5 + 5 + 5 = 18$.

在第一个测试用例中，唯一的一名员工完成了唯一的项目，因此 Monocarp 没有剩余项目。

在第二个测试用例中，第一个月将 $10$ 个项目分配给 $3$ 名员工：每人分得 $3$ 个项目，Monocarp 完成 $1$ 个项目；第二个月将 $11$ 个项目分配给 $4$ 名员工：每人分得 $2$ 个项目，Monocarp 完成 $3$ 个项目。答案为 $1 + 3 = 4$。

在第三个测试用例中，Monocarp 在六个月中完成的项目数分别为 $2$、$1$、$0$、$5$、$5$ 和 $5$。它们的总和为 $2 + 1 + 0 + 5 + 5 + 5 = 18$。