마지막 스테이지

피오라는 게임을 만든다. 지금은 새 게임의 마지막 스테이지를 설계하고 있다.

스테이지는 정사각 격자 위의 미로다. 플레이어는 칸 $(0, 0)$에서 출발해 칸 $(a, b)$까지 가야 한다.

피오라가 쓰는 레벨 편집기에는 블록이 한 종류뿐이다. 이 블록은 서로 수직인 $1 \times n$ 직사각형 두 개가 $1 \times 1$ 칸 하나를 공유하는 L자 모양이고, 블록 하나가 덮는 칸은 $2n - 1$개다. 블록은 네 방향으로 회전해서 놓을 수 있다. 블록끼리 겹칠 수는 없지만 서로 맞닿게 놓는 것은 괜찮다. 플레이어는 블록이 덮은 칸 위를 걸어 다니고, 변을 맞댄 두 칸 사이를 이동한다. 두 칸이 서로 다른 블록에 속해도 이동할 수 있다. 플레이어가 지나는 칸은 모두 블록이 덮고 있으므로 출발 칸과 목표 칸도 블록이 덮는다.

$n = 3$인 블록.

피오라는 플레이어가 $(0, 0)$에서 $(a, b)$까지 갈 수 있게 하면서 블록을 가장 적게 쓰려고 한다. 각 테스트 케이스마다 블록의 최소 개수를 구하라.

첫 줄에 테스트 케이스의 개수 $m$ ($1 \le m \le 100$)이 주어진다. 다음 $m$개의 줄에는 각각 세 정수 $a$, $b$, $n$ ($-10^8 \le a, b \le 10^8$; $2 \le n \le 10^8$)이 주어진다. $a$는 목표 칸의 가로 좌표, $b$는 목표 칸의 세로 좌표이고, $n$은 블록을 이루는 직사각형의 길이다. 목표 칸은 출발 칸과 다르다. 즉 $a \ne 0$이거나 $b \ne 0$이다.

각 테스트 케이스마다 필요한 블록의 최소 개수를 한 줄에 하나씩 출력한다. 개수만 출력하고 블록을 배치한 모양은 출력하지 않는다.