It was a tough battle but the humans won it comprehensively in the end. It was made possible due to combined efforts of both the human tribes but the 2^nd tribe wants to take all the credit and rule the world by killing the first tribe. Now that the war has ended, the tribes would be returning to their cities. The warriors would be travelling over the bridges built earlier, in small groups. It is then that the 2^nd tribe wants to execute their plan. The king of the 1^st tribe knows this and wants to ensure that this doesn’t happen. So he puts a constraint, that it should never happen at any time that the number of people of the 2nd tribe outnumber the number of people of the 1st tribe either on both sides or on the bridge. Also, it is night time and a torch needs to be carried for travel to be possible. But unfortunately, there’s just one torch available and hence atleast someone would have to come back every time, with the torch. To make matters worse, there’s a restriction on the number of warriors that can cross the bridge in one pass.

Input

The first line of input contains test cases t (1<=t<=50). Then t lines follow, one for each test case. It contains three integers, n (1<=n<=100) the number of warriors of first tribe, m (1<=m<=100) the number of warriors of second tribe and c (1<=c<=50) the number of warriors that can cross the bridge in a single pass. 

Output

Display a single line for each test case, containing a single integer which gives the total number of times the bridge is crossed. A round trip counts as 2. Output -1 if travel is not possible with the given constraints.

Example

Input:
3
3 3 2
4 4 2
100 100 20
Output:
11
-1
21