The Final Level

Fiora designs games. She is now laying out the final level of a new game.

A level is a labyrinth on a square grid. The player starts on the square $(0, 0)$ and has to reach the square $(a, b)$.

Fiora works in a level editor that offers a single building block: an L-shaped corner made of two perpendicular $1 \times n$ rectangles that share one $1 \times 1$ square, so one block covers $2n - 1$ squares. A block can be rotated in four ways. Blocks must not overlap, but they may touch. The player walks on any square covered by a block and moves between two squares that share a side, even when the two squares belong to different blocks. Every square on the player's route is covered by a block, so the start square and the goal square are covered as well.

Blocks with $n = 3$.

Fiora wants the level to use as few blocks as possible while the player can still get from $(0, 0)$ to $(a, b)$. Find that minimum for each test case.

The first line has one integer $m$ ($1 \le m \le 100$), the number of test cases. Each of the next $m$ lines has three integers $a$, $b$, $n$ ($-10^8 \le a, b \le 10^8$; $2 \le n \le 10^8$). Here $a$ is the horizontal coordinate of the goal square, $b$ is its vertical coordinate, and $n$ is the length of each rectangle of a block. The goal square is not the start square, so $a \ne 0$ or $b \ne 0$.

For each test case, print the minimal number of blocks on its own line. Print only this number, not the arrangement of the blocks.