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. 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). For each test case, output one integer — the total number of projects that Monocarp will complete himself over (k) months. 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 complet