종이

$1$부터 $n$까지의 정수가 각각 한 장의 종이에 적혀 있습니다. 종이들은 왼쪽에서 오른쪽으로 값이 커지는 순서로 한 줄로 놓여 있어서, 맨 앞 종이에는 $1$이, 맨 뒤 종이에는 $n$이 적혀 있습니다.

이제 다음 동작을 반복합니다.

• 줄의 맨 앞에서 종이 $k$장을 집어 듭니다.
• 그 종이들에 적힌 수를 모두 더합니다.
• 집어 든 종이들을 버리고, 구한 합을 적은 새 종이 한 장을 줄의 맨 뒤에 놓습니다.

어느 순간 남은 종이가 $k$장보다 적다면, 그 동작에서는 남아 있는 종이를 모두 집어 듭니다.

$n$, $k$, $r$가 주어질 때, $r$번째 동작에서 새 종이에 적히는 수를 구하세요.

첫 줄에 질의의 개수를 나타내는 정수 $t$ ($1 \le t \le 100$)가 주어집니다.

이어지는 $t$개의 줄에는 각각 세 정수 $n$, $k$, $r$ ($1 \le n, k, r \le 10^9$)가 공백 하나로 구분되어 주어집니다. 각 줄은 $n$과 $k$로 정해지는 게임에서 $r$번째 동작에 적히는 수를 묻습니다.

$t$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째 질의의 답인 정수 하나를 출력합니다.