You are given three non-negative integers $n$, $k$, and $x$. Find the maximum possible sum of elements in an array consisting of non-negative integers, which has $n$ elements, its MEX is equal to $k$, and all its elements do not exceed $x$. If such an array does not exist, output $-1$.

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. Then follows the description of the test cases.

The only line of each test case contains three integers $n$, $k$, and $x$ ($1 \leq n, k, x \leq 200$).

Output

For each test case, output a single number — the maximum sum of elements in a valid array, or $-1$, if such an array does not exist.

Note

In the first test case, the maximum sum is $7$, and one of the valid arrays is $[0, 1, 2, 2, 2]$.

In the second test case, there are no valid arrays of length $n$.

In the third test case, the maximum sum is $57$, and one of the valid arrays is $[0, 1, 28, 28]$.

Samples

9
5 3 3
4 7 5
4 2 28
12 10 6
57 51 122
200 1 200
2 2 1
3 2 1
4 7 10

7
-1
57
-1
2007
39800
1
2
-1