P13435 [GCJ 2009 #1B] The Next Number

你正在写一个数字列表。对于每个 $1 \leq i \leq 9$，你的列表包含所有十进制表示中恰好有 $D_i$ 个 $i$ 的数。你将这些数按升序排列。 例如，你可能正在写所有恰好包含两个 '1' 和一个 '5' 的数。你的列表将以 115、151、511、1015、1051 开头。 现在，给定 $N$，即你刚刚写下的最后一个数，请你计算列表中的下一个数是多少。

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

对于每个测试用例，输出 Case #$X$: $K$ 其中 $X$ 是测试用例编号（从 1 开始），$K$ 是列表中的下一个整数。

**限制条件** **小数据集（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 完成。