Problem

Freya the Frog is traveling on the 2D coordinate plane. She is currently at point $(0,0)$ and wants to go to point $(x,y)$. In one move, she chooses an integer $d$ such that $0≤d≤k$ and jumps $d$ spots forward in the direction she is facing.

Initially, she is facing the positive $x$ direction. After every move, she will alternate between facing the positive $x$ direction and the positive $y$ direction (i.e., she will face the positive $y$ direction on her second move, the positive $x$ direction on her third move, and so on).

What is the minimum amount of moves she must perform to land on point $(x,y)?$

Input

The first line contains an integer $t(1≤t≤10^4 )$ — the number of test cases.

Each test case contains three integers $x, y,$ and $k (0≤x,y≤10^9,1≤k≤10^9).$

Output

For each test case, output the number of jumps Freya needs to make on a new line.

Example : in

3
9 11 3
0 10 8
1000000 100000 10

Example : out

8
4
199999

Note

In the first sample, one optimal set of moves is if Freya jumps in the following way: $(0,0 ) →(2,0) →(2,2) →(3,2) →(3,5) →(6,5) →(6,8) →(9,8) →(9,11)$. This takes $8$ jumps.