Driving an Icosahedral Rover

After decades of fruitless effort, one of the expedition teams of the ITO (Intersolar Tourism Organization) finally found a planet that is sure to offer one of the finest tourist attractions within ten light-years of our solar system. Besides its comfortable gravity and calm weather, the planet's most striking feature is a region called Mare Triangularis. Despite the name it holds no water; it is a vast plane, uniformly divided into equilateral-triangular sections of equal size, called trigons. This unique landscape is a must-see for tourists, so the board of the ITO decided to invest heavily in the planet.

Despite the intended secrecy, the Society of Astrogeology caught wind of this at once, as always. They immediately sent their president's letter to the Institute of Science and Education of the Commonwealth Galactica, insisting that authoritative academic inspections be completed before any commercial exploitation could damage nature.

Fortunately, the astrogeologists do not intend to inspect every trigon — there are far too many. Inspections are planned only on certain characteristic trigons, and for each of them in one of twenty different scientific aspects.

To speed up construction of the new resort, the ITO's machinery team has already put a brand-new invention into practical use: a rover shaped like an icosahedron, a regular polyhedron with twenty equilateral-triangle faces. It is customized so that each of the twenty faces fits a trigon exactly. Using a built-in high-tech gyromotor, the rover can roll onto one of the three trigons neighboring the one its bottom face rests on.

Figure E.1: The rover on Mare Triangularis

Each of the twenty faces carries its own equipment set, applied to the trigon under the face currently touching the ground. The rover was meant to speed up the construction of luxury hotels for wealthy interstellar travelers, but by swapping the installed equipment sets it can also speed up academic inspections.

Figure E.2: The coordinate system

Figure E.3: Face numbering

You are the driver of this rover, and you are asked to move it onto the trigon designated by the leader of the scientific commission in as few steps as possible. What makes the task harder is that a specific designated face — the one fitted with the appropriate equipment set — must end up on the bottom. The heading (rotation) of the rover does not matter.

The trigons of Mare Triangularis are given two-dimensional coordinates as shown in Figure E.2. As on maps of Earth, the $x$ axis runs from west to east and the $y$ axis from south to north. Every trigon $(x, y)$ has the neighboring trigons $(x - 1, y)$ and $(x + 1, y)$. In addition, when $x + y$ is even it has the neighbor $(x, y + 1)$; otherwise — that is, when $x + y$ is odd — it has the neighbor $(x, y - 1)$.

Figure E.3 shows a development (unfolding) of the rover's skin. The faces shown on top of the development make up the exterior: if the numbers were actually painted on the rover, they would be readable from the outside. These numbers identify the faces.

When you start, the rover is on trigon $(0, 0)$ with face $0$ touching the ground, placed so that rolling north onto trigon $(0, 1)$ brings face $5$ to the bottom.

As your first step you may choose one of the three adjacent trigons $(-1, 0)$, $(1, 0)$, or $(0, 1)$; the bottom then becomes face $4$, $1$, or $5$, respectively. If your first step is to $(1, 0)$, the second step can bring the rover to $(0, 0)$, $(2, 0)$, or $(1, -1)$, making the bottom face $0$, $6$, or $2$, respectively. The rover may visit any trigon two or more times, including the start and the goal trigons, when appropriate.

The theoretical-design section of the ITO has shown that the rover can reach any goal trigon on any specified bottom face within a finite number of steps.

The input consists of a number of datasets. There are at most $50$ datasets.

Each dataset is a single line containing three integers $x$, $y$, and $n$, separated by spaces. Here $(x, y)$ specifies the coordinates of the trigon the rover must reach, and $n$ specifies the face that must end up on the bottom.

The end of the input is indicated by a line containing three zeros.

For each dataset, output a single line containing one integer: the minimum number of steps required to place the rover on the specified trigon with the specified face touching the ground. No other characters may appear in the output.

You may assume that the required number of steps never exceeds $100$. Mare Triangularis is wide enough that none of its edges can be reached within that many steps.