Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Gauss - The Great Mathematician

Limits: 1s, 1.0 GB

Carl Friedrich Gauss was a great mathematician. When he was a child, his teacher told him to sum up all the numbers from 1 to 100 to keep him busy for some time. To his surprise, Gauss solved the problem in a few moments. He contributed in many fields of science. Some of his contributions are used in Computer Science too! #Respect!

In this problem, we want to keep you busy too! You have to find the sum of an arithmetic sequence. In mathematics, an arithmetic sequence is a sequence of numbers such that the difference between two consecutive terms is constant.

Example:

$1, 2, 3, 4, 5, 6, \cdots $

$2, 7, 12, 17, 22, 27, \cdots $

$27, 22, 17, 12, 7, 2, -3, -8, \cdots $

$-8, -3, 2, 7, 12, 17, \cdots $

But in this problem, we are only interested in increasing arithmetic sequence where each term is greater than the previous term. You will be given the first two terms and the last term of an increasing arithmetic sequence. You have to find the sum of all the terms of the given sequence.

Input

The first line of the input will only contain a single integer $T(1\leq T \leq 10^3)$ denoting the number of test cases. In the next $T$ lines, there will be 3 integers $A_1, A_2, A_n$ where $A_1$ is the first term, $A_2$ is the second term and $A_n$ is the last term of the sequence. It is guaranteed that a valid sequence of integers can be formed from the given 3 integers.

Constraints:

$1 \leq T \leq 10^3$

$-10^4 \leq A_1 < A_2 \leq A_n \leq 10^4$

Output

For each test case, print the sum of the sequence in a single line.

Samples

InputOutput
4
1 2 6
-6 -5 -1
2 7 22
-8 -3 17
21
-21
60
27

Discussion