题目描述

Ada 给了 John 一个正整数 $N$。她向他发起挑战，要求通过在给定数字 $N$ 中（任意位置）恰好插入一个数字（$0 \ldots 9$），构造出一个新的数字（没有前导零），且该数字是 $9$ 的倍数。保证 $N$ 没有前导零。

由于 John 喜欢较小的数字，他希望构造出尽可能小的满足条件的数字。你能帮助 John 吗？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例一行，包含一个正整数 $N$：Ada 给 John 的数字。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 John 构造出的新数字。如前所述，$y$ 不能有前导零。

3
5
33
12121

Case #1: 45
Case #2: 333
Case #3: 121212

提示

在样例 #1 中，满足整除约束的构造结果只有两个数字：$45$ 和 $54$。John 选择了较小的数字。

在样例 #2 中，$333$ 是唯一可能的数字。

在样例 #3 中，有 $4$ 种可能的选项：$212121$、$122121$、$121221$ 和 $121212$，其中最小的数字是 $121212$。

限制条件

$1 \le T \le 100$。

测试集 1

$1 \le N \le 10^5$。

测试集 2

最多 $10$ 个测试用例满足：

$1 \le N \le 10^{123456}$。

其余测试用例满足：

$1 \le N \le 10^5$。

翻译由 DeepSeek V4 Pro 完成