You've recently stumbled upon the remains of a ruined ancient city. Luckily, you've studied enough ancient architecture to know how the buildings were laid out.

The city had n buildings in a row. Unfortunately, all but the first two buildings have deteriorated. All you can see in the city are the heights of the first two buildings. The height of the first building is x, and the height of the second building is y.

Your studies show ancient traditions dictate for any three consecutive buildings, the heights of the two smaller buildings sum up to the height of the largest building within that group of three. This property holds for all consecutive triples of buildings in the city. Of course, all building heights were nonnegative, and it is possible to have a building that has height zero.

You would like to compute the sum of heights of all the buildings in the row before they were ruined. You note there can be multiple possible answers, so you would like to compute the minimum possible sum of heights that is consistent with the information given. It can be proven under given constraints that the answer will fit within a 64-bit integer.

Input Format

The first line of the input will contain an integer T, denoting the number of test cases.
Each test case will be on a single line that contains 3 integers x, y, n.

Output Format

Print a single line per test case, the minimum sum of heights of all buildings consistent with the given information.

Constraints

For all files
1 ≤ T ≤ 10,000
0 ≤ x, y
2 ≤ n

File 1 -- 61 pts:
x, y, n ≤ 10

File 2 -- 26 pts:
x, y, n ≤ 100

File 3 -- 13 pts:
x, y, n ≤ 1,000,000,000