Description

你正在写一个数字列表。对于每个 $1 \leq i \leq 9$，你的列表包含所有十进制表示中恰好有 $D_i$ 个 $i$ 的数。你将这些数按升序排列。

例如，你可能正在写所有恰好包含两个 '1' 和一个 '5' 的数。你的列表将以 115、151、511、1015、1051 开头。

现在，给定 $N$，即你刚刚写下的最后一个数，请你计算列表中的下一个数是多少。

Input Format

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来 $T$ 行，每行一个整数 $N$。

Output Format

对于每个测试用例，输出

Case #$X$: $K$

其中 $X$ 是测试用例编号（从 1 开始），$K$ 是列表中的下一个整数。

3
115
1051
6233

Case #1: 151
Case #2: 1105
Case #3: 6323

Hint

限制条件

小数据集（9 分）

• 时间限制：2 秒。
• $1 \leq T \leq 50$
• $1 \leq N \leq 10^6$

大数据集（26 分）

• 时间限制：3 秒。
• $1 \leq T \leq 500$
• $1 \leq N \leq 10^{20}$

翻译由 ChatGPT-4.1 完成。