Esraa, Morgan, Hussein and Yasser didn’t love geometry but Abdelkarim loved it so much. Abdelkarim (the coach) decided to challenge them, he gave them a linear function and he wanted them to calculate the area between the line, x-axis and y-axis.

They want you to help them solve this problem. You will be given a, b, c as ay = bx + c.

Find the area between this line, x-axis and y-axis

It is guaranteed that the area is an integer number.

it is guaranteed that the line is not parallel to x or y-axis.

Input

The first line of input begins with a line containing T the number of test cases.

Each test case starts with a line contains three separated integer numbers a, b, c  (-10⁹ ≤ a, b, c ≤ 10⁹.)

Output

For each test case print a line contains the area between the x-axes, y-axis and the line .

Example

Input:
2
2 4 8
2 4 0

Output:
4
0