小约翰刚在学校开始学习加法运算。他的母亲想出了一个新游戏来帮助约翰学习。游戏开始时，约翰的母亲在不同的纸片上写下了从 $1$ 到 $n$ 的所有整数。然后，她将这些纸片排成一行，保持数字的顺序不变（从 $1$ 到 $n$）。约翰的任务是执行给定操作若干次。该操作包括：从行首拿起 $k$ 张纸片，将这些纸片上的数字相加，撕掉并扔掉这些纸片，将得到的和写在一张新纸片上，并将其放在这一行的末尾。如果在游戏的某个时刻，行中的纸片少于 $k$ 张，约翰不必担心，他会将剩余所有纸片上的数值相加。

约翰非常喜欢这个新游戏。他不断要求母亲检查他在计算连续的和时是否犯了错误。此外，约翰玩这个游戏玩得非常好，所以他尝试挑战越来越大的 $n$ 和 $k$ 值。约翰的母亲无法跟上检查约翰所得结果的速度，因此她请求你编写一个程序来为她验证结果。

编写一个程序，完成以下任务：

• 从标准输入读取数字 $n$、$k$ 和 $r$。
• 计算约翰在第 $r$ 次操作中应该写下的和。
• 将结果写入标准输出。

输入格式

标准输入的第一行包含一个整数 $t$ ($1 \le t \le 100$)，表示需要处理的查询数量。每个查询位于单独的一行，由三个整数 $n$、$k$ 和 $r$ ($1 \le n, k, r \le 10^{9}$) 组成，并以空格分隔。该查询要求计算在参数为 $n$ 和 $k$ 的游戏中，约翰在第 $r$ 次操作中应该写下的数字。

输出格式

输出应包含 $t$ 行。第 $i$ 行应包含一个整数，即第 $i$ 个查询的答案。

样例

输入 1

6
6 2 1
6 2 2
6 2 3
6 2 4
6 2 5
6 2 6

输出 1

3
7
11
10
21
21