Mirror Trap

A mirror trap is a rectangular box whose six inner faces are all mirrors, with the reflecting sides facing the interior. Its dimensions are $2x \times 2y \times 2z$, where $x, y, z$ are positive integers. Exactly at the centre sits a point laser whose size is negligible. Introduce a Cartesian coordinate system whose axes are parallel to the edges of the box, with the laser at the origin; the box then occupies $[-x, x] \times [-y, y] \times [-z, z]$.

The laser may be aimed at any integer lattice point inside the box (points on the mirror surfaces included, with the single exception of the origin $(0,0,0)$). The fired beam reflects off the mirrors, and its travelled distance is measured in the Manhattan (city) metric: the sum of the distances travelled parallel to each of the three axes.

Choose the aiming direction so that the beam satisfies all of the following, and report the maximum possible total travelled distance:

• it is reflected by the mirrors (not necessarily by all of them),
• it never crosses an edge (where two faces meet) or a vertex of the box,
• it returns to the laser (possibly from a different direction).

Edges and vertices do not reflect the beam.

Note: several aim points may attain the maximum, so instead of an aim point this problem asks for the maximum total travelled distance itself (a single integer).

A single input describes several mirror traps. The first line contains the number of traps $K$ ($1 \le K \le 1000$). Each of the next $K$ lines describes one trap as three space-separated integers $x, y, z$ ($5 \le x, y, z \le 1000$); that trap has dimensions $2x \times 2y \times 2z$.

Print exactly $K$ lines. The $i$-th line contains a single integer: the maximum total distance the beam can travel in the $i$-th trap while satisfying all of the conditions above.