## 1. Abridged problem statement

Given a rectangular 3D grid of cabins of size `X × Y × Z`. Two cabins are connected by a passageway iff their centers are at Euclidean distance `1`, i.e. they are adjacent along one coordinate axis.

A group of Jedis must walk together through the cube, placing a bomb in every passageway. They may traverse passageways multiple times. They start and finish in surface cabins, possibly the same one. For each input line containing `X Y Z`, output the minimum possible walk length needed to traverse every passageway at least once.

Output format:

```text
Case #k: answer
```

---

## 2. Detailed editorial

Model the Death Cube as an undirected grid graph:

- Vertices are cabins.
- Edges are passageways between adjacent cabins.
- We need the shortest walk that covers every edge at least once.
- The walk may start and end anywhere on the surface.

This is the **open Chinese Postman Problem** on a rectangular grid graph.

---

### Step 1: Count the number of passageways

The graph has edges in three directions.

Along the `X` direction:

```text
(X - 1) * Y * Z
```

Along the `Y` direction:

```text
X * (Y - 1) * Z
```

Along the `Z` direction:

```text
X * Y * (Z - 1)
```

So:

```text
E = (X - 1)YZ + X(Y - 1)Z + XY(Z - 1)
```

Every edge must be traversed at least once, so the answer is:

```text
E + extra
```

where `extra` is the minimum number of repeated edges.

---

### Step 2: Euler trail condition

A connected undirected graph has an Euler trail using every edge exactly once if it has either:

- `0` odd-degree vertices, giving an Euler circuit, or
- `2` odd-degree vertices, giving an Euler path between them.

If there are more odd-degree vertices, we must repeat some edges.

Repeating every edge along a path between vertices `u` and `v` changes degree parity only at `u` and `v`. Therefore, fixing the graph means pairing odd vertices and duplicating shortest paths between paired vertices.

Because this is a grid graph, shortest path distance is Manhattan distance.

Since the route is allowed to be open, two odd vertices may be left unpaired as the start and finish.

---

### Step 3: Sort dimensions

The formula depends only on the side lengths, not on their order. Let:

```text
a <= b <= c
```

be the sorted dimensions.

---

## Case A: `a = 1`, flat 2D grid

If `a = 1`, the graph is a `b × c` rectangular 2D grid.

If also `b = 1`, the graph is just a path of length `c - 1`, so no edge needs to be repeated:

```text
extra = 0
```

Otherwise, the optimal number of repeated edges in a `b × c` grid is:

```text
extra = b + c - 5
```

with one extra if both `b` and `c` are odd:

```text
extra = b + c - 5 + [b odd and c odd]
```

For very small grids this expression may become negative, so we clamp it to zero:

```text
extra = max(0, b + c - 5 + [b odd and c odd])
```

---

## Case B: `a >= 2`, genuine 3D grid

Assume all dimensions are at least `2`.

A vertex degree depends on how many of its coordinates are on the boundary.

For a dimension of length greater than `1`:

- boundary coordinate contributes `1` neighbor along that axis,
- interior coordinate contributes `2` neighbors along that axis.

So a vertex has odd degree iff an odd number of its coordinates are boundary coordinates.

Thus odd vertices are:

1. Face-interior vertices: exactly one boundary coordinate.
2. Corners: exactly three boundary coordinates.

Vertices on box edges but not corners have exactly two boundary coordinates, hence even degree.

---

### Bulk face contribution

Consider one pair of opposite faces of size `p × q`. Ignoring its boundary, the face interior is a grid of size:

```text
(p - 2) × (q - 2)
```

The two opposite faces together contribute:

```text
(p - 2)(q - 2)
```

repeated edges in the regular domino-like pairing.

Summing over the three orientations gives the bulk term:

```text
base =
    (a - 2)(b - 2)
  + (a - 2)(c - 2)
  + (b - 2)(c - 2)
```

The remaining cost is caused by corners and parity leftovers near the boundary. This is a small constant depending on the thinnest dimension `a` and, for `a = 3`, the parity of `b` and `c`.

---

### Boundary correction

The correction is:

```text
if a == 2:
    correction = 3
elif a == 3:
    correction = 6, 7, or 9
else:
    correction = 9
```

More precisely, for `a = 3`:

```text
number of odd values among b and c = 0 -> correction = 6
number of odd values among b and c = 1 -> correction = 7
number of odd values among b and c = 2 -> correction = 9
```

So:

```text
correction = [6, 7, 9][(b mod 2) + (c mod 2)]
```

Therefore, for `a >= 2`:

```text
extra = base + correction
```

---

### Final formula

Let `a <= b <= c`.

Number of edges:

```text
edges = (X - 1)YZ + X(Y - 1)Z + XY(Z - 1)
```

Extra repeated edges:

```text
if a == 1 and b == 1:
    extra = 0
elif a == 1:
    extra = max(0, b + c - 5 + [b odd and c odd])
else:
    base = (a - 2)(b - 2) + (a - 2)(c - 2) + (b - 2)(c - 2)

    if a == 2:
        correction = 3
    elif a == 3:
        correction = [6, 7, 9][(b mod 2) + (c mod 2)]
    else:
        correction = 9

    extra = base + correction
```

Answer:

```text
edges + extra
```

The computation is `O(1)` per test case.

---

## 3. Provided C++ solution with detailed comments

```cpp
#include <bits/stdc++.h> // Includes almost all standard C++ library headers.

using namespace std; // Allows using standard library names without std:: prefix.

// Overload output operator for pairs.
// This helper is not actually needed for the final solution, but is part of the template.
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second; // Print first and second separated by a space.
}

// Overload input operator for pairs.
// Also unused in this particular solution.
template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second; // Read first and second from input.
}

// Overload input operator for vectors.
// Reads every element of the vector.
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) { // Iterate by reference over all vector elements.
        in >> x;      // Read one element.
    }
    return in;        // Return stream to allow chaining.
};

// Overload output operator for vectors.
// Prints elements separated by spaces.
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {  // Iterate over vector elements.
        out << x << ' '; // Print element followed by a space.
    }
    return out;       // Return stream to allow chaining.
};

// Global variables storing one test case.
int64_t x, y, z;

// Reads one test case.
// Returns true if three integers were successfully read, false at EOF.
bool read() { return bool(cin >> x >> y >> z); }

// Solves one test case using the closed-form formula.
void solve() {
    // Put dimensions into an array so we can sort them.
    array<int64_t, 3> d = {x, y, z};

    // The formula depends only on the sorted side lengths.
    sort(d.begin(), d.end());

    // Structured binding: a <= b <= c.
    auto [a, b, c] = d;

    // Count all original passageways/edges of the 3D grid.
    //
    // Edges parallel to X-axis: (x - 1) * y * z
    // Edges parallel to Y-axis: x * (y - 1) * z
    // Edges parallel to Z-axis: x * y * (z - 1)
    int64_t edges = (x - 1) * y * z + x * (y - 1) * z + x * y * (z - 1);

    // This will store the minimum number of repeated edges.
    int64_t extra;

    // Case 1: a == 1 and b == 1.
    // The grid is a simple 1D path of length c - 1.
    // A path already has an Euler trail, so no repeats are needed.
    if(a == 1 && b == 1) {
        extra = 0;
    }

    // Case 2: a == 1 but b > 1.
    // The graph is a 2D b x c rectangular grid.
    else if(a == 1) {
        // For a 2D grid, the known minimum repeated edge count is:
        // b + c - 5, plus 1 if both dimensions are odd.
        //
        // max with 0 handles very small grids such as 2 x 2,
        // where no repetition is needed.
        extra = max<int64_t>(0, b + c - 5 + (b % 2 == 1 && c % 2 == 1));
    }

    // Case 3: all dimensions are at least 2, so this is a real 3D box.
    else {
        // Bulk contribution from pairing odd-degree vertices inside faces.
        //
        // For every pair of opposite faces, the face interior has size
        // (p - 2) x (q - 2). The two opposite faces together contribute
        // (p - 2)(q - 2) repeated edges.
        //
        // Sum over the three choices of face orientation.
        int64_t base =
            (a - 2) * (b - 2) +
            (b - 2) * (c - 2) +
            (a - 2) * (c - 2);

        // Remaining small correction caused by corners and parity leftovers.
        int64_t correction;

        // If the smallest dimension is 2, opposite corners across the thin
        // direction are adjacent, so three repeated edges suffice.
        if(a == 2) {
            correction = 3;
        }

        // If the smallest dimension is 3, the correction depends on the parity
        // of b and c.
        else if(a == 3) {
            // b % 2 + c % 2 is:
            // 0 if both are even,
            // 1 if exactly one is odd,
            // 2 if both are odd.
            //
            // The corresponding corrections are 6, 7, and 9.
            correction = array<int64_t, 3>{6, 7, 9}[b % 2 + c % 2];
        }

        // For all thicker boxes, the correction stabilizes at 9.
        else {
            correction = 9;
        }

        // Total repeated edges are the bulk face contribution plus correction.
        extra = base + correction;
    }

    // The total walk length is every original edge once plus repeated edges.
    cout << edges + extra << '\n';
}

int main() {
    // Speeds up C++ I/O by detaching iostreams from stdio.
    ios_base::sync_with_stdio(false);

    // Prevents automatic flushing of cout before cin.
    cin.tie(nullptr);

    // Test cases are read until EOF.
    // Numbering starts from 1.
    for(int test = 1; read(); test++) {
        // Print required case prefix.
        cout << "Case #" << test << ": ";

        // Solve and print the answer for this test case.
        solve();
    }

    // Successful program termination.
    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
import sys


def solve_case(x, y, z):
    """
    Return the minimum walk length needed to traverse every passageway
    in an x by y by z rectangular grid graph.
    """

    # Sort dimensions because the formula depends only on side lengths,
    # not on which axis is called X, Y, or Z.
    a, b, c = sorted((x, y, z))

    # Count original passageways.
    #
    # Along X direction there are (x - 1) * y * z edges.
    # Along Y direction there are x * (y - 1) * z edges.
    # Along Z direction there are x * y * (z - 1) edges.
    edges = (x - 1) * y * z + x * (y - 1) * z + x * y * (z - 1)

    # Compute the minimum number of repeated edges.
    if a == 1 and b == 1:
        # The graph is just a 1D path.
        # A path can be traversed completely without repeating edges.
        extra = 0

    elif a == 1:
        # The graph is a 2D b x c grid.
        #
        # The optimal extra cost is b + c - 5,
        # plus one if both dimensions are odd.
        #
        # For very small grids, this value may be negative,
        # so clamp it to zero.
        both_odd = (b % 2 == 1 and c % 2 == 1)
        extra = max(0, b + c - 5 + int(both_odd))

    else:
        # Genuine 3D case: all dimensions are at least 2.

        # Bulk contribution from pairing odd-degree vertices in face interiors.
        base = (
            (a - 2) * (b - 2)
            + (a - 2) * (c - 2)
            + (b - 2) * (c - 2)
        )

        # Small correction from corners and parity leftovers.
        if a == 2:
            correction = 3
        elif a == 3:
            # Number of odd values among b and c.
            parity_count = (b % 2) + (c % 2)

            # Corrections:
            # 0 odd dimensions -> 6
            # 1 odd dimension  -> 7
            # 2 odd dimensions -> 9
            correction = [6, 7, 9][parity_count]
        else:
            correction = 9

        extra = base + correction

    # The final route length is all original edges plus repeated edges.
    return edges + extra


def main():
    # Read all integers from input.
    data = list(map(int, sys.stdin.read().split()))

    # Each test case consists of exactly three integers: X, Y, Z.
    case_no = 1
    out = []

    for i in range(0, len(data), 3):
        x, y, z = data[i], data[i + 1], data[i + 2]

        ans = solve_case(x, y, z)

        out.append(f"Case #{case_no}: {ans}")

        case_no += 1

    # Print all answers at once.
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()
```

---

## 5. Compressed editorial

Treat the cube as an undirected grid graph. We need the shortest walk covering every edge, so the answer is:

```text
number_of_edges + minimum_repeated_edges
```

The number of edges is:

```text
E = (X - 1)YZ + X(Y - 1)Z + XY(Z - 1)
```

The repeated edges are needed only to fix odd-degree vertices. Repeating a path flips parity at its two endpoints, so we pair odd vertices by shortest paths, leaving up to two odd vertices as start and finish.

Sort dimensions:

```text
a <= b <= c
```

If `a = b = 1`, the graph is a path:

```text
extra = 0
```

If `a = 1`, the graph is a 2D grid:

```text
extra = max(0, b + c - 5 + [b odd and c odd])
```

Otherwise all dimensions are at least `2`. Odd vertices are face-interior vertices and corners. The face-interior contribution is:

```text
base =
    (a - 2)(b - 2)
  + (a - 2)(c - 2)
  + (b - 2)(c - 2)
```

The remaining corner/parity correction is:

```text
if a == 2:
    correction = 3
elif a == 3:
    correction = [6, 7, 9][(b % 2) + (c % 2)]
else:
    correction = 9
```

Then:

```text
extra = base + correction
answer = E + extra
```

Each test case is solved in `O(1)`.