Metro Manila Detour

Metro Manila has six circumferential roads, C1 through C6, laid out as concentric semicircles around the center (Manila), and ten radial roads, R1 through R10, that run outward from the center. R1 is the southernmost radial road and R10 is the northernmost, and the numbering follows that order along the semicircle. C6 is still under construction, but assume it is passable in this problem.

An intersection is the point where circumferential road Cc meets radial road Rr, written (Cc, Rr). The center is (C0, R0).

Distances are counted like this.

• One segment of a radial road, between (Cc, Rr) and (Cc+1, Rr), is 1. The center to (C1, Rr) is also 1. For instance, (C1, R3) to (C2, R3) is 1.
• One arc of circumferential road Cc, between (Cc, Rr) and (Cc, Rr+1), is c. For instance, (C3, R1) to (C3, R2) is 3.
• The circumferential roads are semicircles, so R1 and R10 sit at the two ends and no arc joins them directly.

Under the number coding scheme a vehicle may not drive along the radial road whose number equals the last digit of its plate. A vehicle with plate ABC-123 ends in 3, so it cannot use R3, and a vehicle whose plate ends in 0 cannot use R10. Each last digit closes one circumferential road as well, and only C6 stays open at all times.

Only driving along a closed road is forbidden. A vehicle may stand at an intersection of a closed road and may cross that road. So the shortest distance from (C1, R2) to (C5, R1) is 5 for plate ABC-123 (the darkened path in the figure) and 9 for plate CBA-321. Some vehicles cannot reach the destination at all.

Given the starting point, the destination and the last digit of the plate, find the shortest distance from the starting point to the destination.

The input holds several test cases. Each test case is five single digit numbers separated by whitespace: c1 r1 c2 r2 d. (Cc1, Rr1) is the starting point, (Cc2, Rr2) is the destination, and d is the last digit of the plate number. A radial number of 0 means R10. A circumferential number of 0 means the center, and the radial number is 0 as well in that case. No blank line appears between test cases, and a line holding a single 0 follows the last test case.

For each test case print one line in the form Case x: y, where x is the test case number starting at 1 and y is the shortest distance. Print Case x: not possible instead when the destination cannot be reached.