5.2 Find Odds!!!

Score: 30pts

Time Limit: 5.00 sec

In a culinary adventure, Dumbo finds himself exploring an array of numbers. This array is quite unique, consisting of the first N+K-1 positive odd numbers, appearing only once each. However, there's a twist: among these numbers, there's one special digit that appears not just once, but K times!

Dumbo has also calculated the sum of all these numbers in his array, and he's called it S. Now, he's turning to you for assistance. He wants you to unveil the mystery and identify the specific number that occurs K times in his array.

For instance, imagine Dumbo has N=3 and K=2, which means he has a collection of the first three odd numbers. There could be various combinations like [1,1,3,5], [3,1,3,5], or [5,3,5,1], but only one of these arrays is the answer.

Your task is to solve this riddle by providing Dumbo with the number that appears K times in his array, given N, K, and S. Rest assured, there's always a valid array that sums up to S with the specified conditions.

Dumbo has also calculated the sum of all these numbers in his array, and he's called it S. Now, he's turning to you for assistance. He wants you to unveil the mystery and identify the specific number that occurs K times in his array.

For instance, imagine Dumbo has N=3 and K=2, which means he has a collection of the first three odd numbers. There could be various combinations like [1,1,3,5], [3,1,3,5], or [5,3,5,1], but only one of these arrays is the answer.

Your task is to solve this riddle by providing Dumbo with the number that appears K times in his array, given N, K, and S. Rest assured, there's always a valid array that sums up to S with the specified conditions.

Constraints

- T: The value of T (test cases) ranges from 1 to 1000.

- N: N represents a positive integer, and its value can range from 1 to 10^4 (10,000).

- S: S is another positive integer, with values ranging from 1 to 10^9 (1 billion).

- K: K is a positive integer as well, and it has values ranging from 2 to 10^4 (10,000).

- N: N represents a positive integer, and its value can range from 1 to 10^4 (10,000).

- S: S is another positive integer, with values ranging from 1 to 10^9 (1 billion).

- K: K is a positive integer as well, and it has values ranging from 2 to 10^4 (10,000).

Input Format

-The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

-The first and only line of each test case contains three space-separated integers N,K,S.

-The first and only line of each test case contains three space-separated integers N,K,S.

Output Format

For each test case, print a single line containing the integer which appeared K times in Dumbo's array.

Example 1

Input:

3

3 2 14

5 4 28

2 3 10

Output:

5

1

3

Explanation:

Test case 1: Dumbo's array could be [5,3,5,1]

Test case 3: Dumbo's array could be [3,1,3,3]

3

3 2 14

5 4 28

2 3 10

Output:

5

1

3

Explanation:

Test case 1: Dumbo's array could be [5,3,5,1]

Test case 3: Dumbo's array could be [3,1,3,3]