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
In the first sample case, the city had 5 buildings, and the first building has height 10 and the second building has height 7. We know the third building either had height 17 or 3. One possible sequence of building heights that minimizes the sum of heights is {10, 7, 3, 4, 1}. The sum of all heights is 10+7+3+4+1 = 25.
In the second sample case, note that it's possible for some buildings to have height zero.
