---
# System prepended metadata

title: 'Even Digits (8pts, 15pts)'
tags: [Google Kick Start 2018]

---

## Problem
Supervin 有一個特殊的計算機。這個計算機只有一個顯示器、一個加法按鈕和一個減法按鈕。而現在顯示器上有一個整數 **N**。

按下加法按鈕會使得顯示器上的數字增加 1。同樣地，按下減法按鈕會使得顯示器上的數字減少 1。顯示器不會顯示任何前導零。舉例而言，如果顯示器上的數字是 100，則按下減法按鈕會使得數字變為 99，而非 099。

Supervin 不喜歡奇數位數，因為他覺得他們很"奇怪" (nt.1)。因此他希望能在只使用加減法按鈕的前提下，讓顯示器上的數字以十進制表示時只會有偶數的位數。又由於計算機已經有年代了，上面的按鈕不好按，他希望能夠按最少次的按鈕來達到目標。

請你幫 Supervin 找到能讓顯示器上的數字沒有奇數位數所需最少的按按鈕次數。

## Input
第一行會輸入一個整數 **T**，表示接下來輸入測資的數量。緊接著會有 **T** 筆測資，每一筆測資都佔一行且包含一個整數 **N**，即顯示器上的初始數字。

## Output
對每筆測資而言，均印出一行格式為 `Case #x: y` 的字串，其中 x 表示測資編號 (從 1 開始)，而 y 表示上述所需最少的按按鈕次數。

## Limits
$1 \le$ **T** $\le 100$
時間限制：每一測資組 20 秒
記憶體限制：1 GB

### Small dataset (測資組 1)
$1 \le$ **N** $\le 10^5$

### Large dataset (測資組 2)
$1 \le$ **N** $\le 10^{16}$

## Sample
Sample Input
```
4
42
11
1
2018
```

Sample Output
```
Case #1: 0
Case #2: 3
Case #3: 1
Case #4: 2
```

在第一筆測資中，初始數字並沒有奇數位數，因此不需要按按鈕，輸出 0。

在第二筆測資中，按下 3 次減法按鈕可以使得數字變為 8，而不存在小於 3 次且滿足條件的可能。

在第三筆測資中，按下 1 次減法按鈕或加法按鈕可使數字變為 0 或 2，均滿足條件。

在第四筆測資中，按下 2 次加法按鈕可以使得數字變為 2020，而不存在小於 2 次且滿足條件的可能。

## Test Data
[Download Dataset](https://codejam.googleapis.com/dashboard/get_file/AQj_6U1AwEU9tswEcnph5So-f0waahzqlAxVPd6dOQYVJ0tzBHMZOnrkNp3FiGR9C82ZAZENB9ZeGw/test_data.zip?dl=1)

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

#define ll long long

ll findLNum(ll n) {
    string s = to_string(n);
    bool flag = false;
    for (char& c : s) {
        if (flag) {
            c = '0';
        } else if (c == '9') {
            return -1;
        } else if ((c - 48) % 2) {
            flag = true;
            ++c;
        }
    }
    return stoll(s);
}

ll findSNum(ll n) {
    string s = to_string(n);
    bool flag = false;
    for (char& c : s) {
        if (flag) {
            c = '8';
        } else if ((c - 48) % 2) {
            flag = true;
            --c;
        }
    }
    return stoll(s);
}

ll solve(ll n) {
    ll lNum = findLNum(n), sNum = findSNum(n);
    if (lNum < 0 || n - sNum < lNum - n) return n - sNum;
    return lNum - n;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    for (int i = 0; i < t; ++i) {
        ll n; cin >> n;
        cout << "Case #" << i + 1 << ": " << solve(n) << '\n';
    }
}
```
:::

## Notes
nt.1: 在英文中奇數 (odd number) 和奇怪 (odd) 是同一個字。