Description

Tatiana 喜欢保持整洁。她的玩具按照从小到大的顺序排列，她的铅笔按照从短到长的顺序排列，她的电脑按照从旧到新的顺序排列。一天，在练习数数的时候，她注意到有些整数在十进制下书写且没有前导零时，其各位数字是非递减排列的。例如 8、123、555 和 224488 就是这样的数。她决定把这些数称为“tidy”数。不满足这个性质的数，比如 20、321、495 和 999990，就不是 tidy 数。

她刚刚从 1 开始按升序数到了 $N$。她数到的最后一个 tidy 数是多少？

Input Format

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

Output Format

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Tatiana 数到的最后一个 tidy 数。

4
132
1000
7
111111111111111110

Case #1: 129
Case #2: 999
Case #3: 7
Case #4: 99999999999999999

Hint

样例解释

注意，最后一个样例不会出现在 Small 数据集里。

限制条件

• $1 \leq T \leq 100$。

Small 数据集（5 分，测试集 1 - 可见）

• $1 \leq N \leq 1000$。

Large 数据集（10 分，测试集 2 - 隐藏）

• $1 \leq N \leq 10^{18}$。

由 ChatGPT 4.1 翻译