<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

471. Funny Game
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Goryinyich and vot decided to play the following funny game.

Initially some natural number is written on the board. Players move in turns, Goryinyich starts the game. In each turn, player wipes the board out and writes new number equal to the difference between erased number and number chosen by the player. Player may choose any number between one and sum of squares of digits of number that is written on the board. If minimal number is written on the board, the player who got the number in his turn is considered to win. Minimal number is the smallest possible number with a given length and given sum of squares of its digits.

Consider the example. Suppose that number 20 is written on the board. Goryinyich may subtract any number from 1 to 22+02=4 from it. Any of these possibilities makes the number minimal in the abovementioned sense, so Goryinyich wins the game. But after the game was proposed by Goryinyich, vot claimed that Goryinyich went crazy, oversolved problems from Ural championships and vot will never play a game with such cumbersome and tedious rules. Instead, he proposed another game which, in his opinion, is much simpler and more cheerful.

Goryinyich and vot agree on some natural number N. Then vot writes some integer number a from 1 to N on a piece of paper and Goryinyich, unaware of the number written by vot, writes number b (also from 1 to N). If |a-b|=1, then vot pays 1 dollar to Goryinyich, otherwise Goryinyich pays the same to vot.

Your task is to find expected gain of Goryinyich. Of course, you should realize that the players are not stupid (actually, they even also participate in computer programming contests from time to time), so everybody will do his best to maximize expected gain from the game.

Input
Input file contains up to 10 lines, each containing number N from the problem statement (1 ≤ N ≤ 50).

Output
For every N in the input file write to the output file on a separate line the required number as an irreducible fraction. Minus sign, if necessary, should be in the numerator. Follow the format shown in the example below.

Example(s)
sample input
sample output
1
2
Case #1: -1/1
Case #2: 0/1

<|response|>
## 1. Abridged problem statement

For each given `N` (`1 ≤ N ≤ 50`):

- vot secretly chooses an integer `a` from `1..N`.
- Goryinyich chooses an integer `b` from `1..N`, without knowing `a`.
- If `|a - b| = 1`, Goryinyich gains `1` dollar.
- Otherwise, Goryinyich loses `1` dollar.

Both players play optimally, possibly using randomized strategies.

For every input `N`, output Goryinyich’s expected gain as an irreducible fraction:

```text
Case #k: numerator/denominator
```

---

## 2. Key observations needed to solve the problem

The long first game in the statement is irrelevant. We only need the second game.

This is a finite zero-sum game.

Let Goryinyich choose number `i` with probability `q_i`.

For a fixed choice `a` by vot, Goryinyich wins exactly when he chooses `a - 1` or `a + 1`.

So the winning probability against `a` is:

\[
q_{a-1} + q_{a+1}
\]

where missing indices outside `1..N` are treated as `0`.

If Goryinyich wins with probability `p`, his expected gain is:

\[
p \cdot 1 + (1-p) \cdot (-1) = 2p - 1
\]

Therefore, if

\[
\alpha = \max_q \min_a(q_{a-1} + q_{a+1})
\]

then the answer is:

\[
2\alpha - 1
\]

So the problem becomes finding the best possible minimum winning probability.

---

## 3. Full solution approach based on the observations

We want to maximize `t` such that there exists a probability distribution `q` with:

\[
q_{a-1} + q_{a+1} \ge t
\]

for all `a`.

Also:

\[
\sum q_i = 1,\quad q_i \ge 0
\]

Now scale the variables:

\[
x_i = \frac{q_i}{t}
\]

Then:

\[
x_{a-1} + x_{a+1} \ge 1
\]

and:

\[
\sum x_i = \frac{1}{t}
\]

So maximizing `t` is equivalent to minimizing:

\[
\gamma = \sum x_i
\]

subject to:

\[
x_{a-1} + x_{a+1} \ge 1,\quad x_i \ge 0
\]

Then:

\[
\alpha = \frac{1}{\gamma}
\]

The constraints split by parity:

- Odd `a` constraints use only even-indexed `x`.
- Even `a` constraints use only odd-indexed `x`.

After analyzing these independent path-like covering problems, we get closed forms.

---

### Case 1: `N = 1`

There is no pair with distance `1`.

Goryinyich always loses.

\[
\text{answer} = -1
\]

---

### Case 2: `N` is odd

Let:

\[
N = 2m + 1
\]

Then:

\[
\gamma = m + 1 = \frac{N+1}{2}
\]

So:

\[
\alpha = \frac{1}{\gamma} = \frac{2}{N+1}
\]

Expected gain:

\[
2\alpha - 1 = \frac{4}{N+1} - 1 = \frac{3-N}{N+1}
\]

---

### Case 3: `N` is divisible by `4`

Let:

\[
N = 4k
\]

Then:

\[
\gamma = \frac{N}{2}
\]

So:

\[
\alpha = \frac{2}{N}
\]

Expected gain:

\[
2\alpha - 1 = \frac{4}{N} - 1 = \frac{4-N}{N}
\]

---

### Case 4: `N ≡ 2 mod 4`

Then:

\[
\gamma = \frac{N}{2} + 1 = \frac{N+2}{2}
\]

So:

\[
\alpha = \frac{2}{N+2}
\]

Expected gain:

\[
2\alpha - 1 = \frac{4}{N+2} - 1 = \frac{2-N}{N+2}
\]

---

### Final formulas

For each `N`:

- If `N = 1`:

\[
-1
\]

- If `N` is odd:

\[
\frac{3-N}{N+1}
\]

- If `N % 4 == 0`:

\[
\frac{4-N}{N}
\]

- If `N % 4 == 2`:

\[
\frac{2-N}{N+2}
\]

Then reduce the fraction using `gcd`.

Time complexity per test case is:

\[
O(1)
\]

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

pair<int64, int64> solve_one(int n) {
    int64 numerator, denominator;

    // Special case:
    // If N = 1, both players must choose 1.
    // Then |a - b| = 0, so Goryinyich always loses.
    if (n == 1) {
        return {-1, 1};
    }

    // Closed-form formulas derived from the minimax / covering analysis.
    if (n % 2 == 1) {
        // N is odd:
        // answer = (3 - N) / (N + 1)
        numerator = 3 - n;
        denominator = n + 1;
    } else if (n % 4 == 0) {
        // N is divisible by 4:
        // answer = (4 - N) / N
        numerator = 4 - n;
        denominator = n;
    } else {
        // N is even but not divisible by 4, so N == 2 mod 4:
        // answer = (2 - N) / (N + 2)
        numerator = 2 - n;
        denominator = n + 2;
    }

    // Reduce the fraction.
    int64 g = gcd(llabs(numerator), denominator);
    numerator /= g;
    denominator /= g;

    return {numerator, denominator};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int case_id = 1;

    // Input contains up to 10 lines, but reading until EOF is simplest.
    while (cin >> n) {
        auto [num, den] = solve_one(n);

        cout << "Case #" << case_id << ": " << num << "/" << den << '\n';

        case_id++;
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
from math import gcd


def solve_one(n: int) -> tuple[int, int]:
    """
    Return Goryinyich's optimal expected gain as an irreducible fraction.

    The final formulas are:

    N = 1:
        -1/1

    N odd:
        (3 - N) / (N + 1)

    N divisible by 4:
        (4 - N) / N

    N == 2 mod 4:
        (2 - N) / (N + 2)
    """

    # Special case: there is no possible pair with distance 1.
    if n == 1:
        return -1, 1

    if n % 2 == 1:
        # Odd N.
        numerator = 3 - n
        denominator = n + 1
    elif n % 4 == 0:
        # N divisible by 4.
        numerator = 4 - n
        denominator = n
    else:
        # N == 2 mod 4.
        numerator = 2 - n
        denominator = n + 2

    # Reduce the fraction.
    g = gcd(abs(numerator), denominator)
    numerator //= g
    denominator //= g

    return numerator, denominator


def main() -> None:
    data = sys.stdin.read().strip().split()

    for case_id, token in enumerate(data, start=1):
        n = int(token)

        numerator, denominator = solve_one(n)

        print(f"Case #{case_id}: {numerator}/{denominator}")


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