P13159 [GCJ 2017 Qualification] Tidy Numbers

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

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

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

**样例解释** 注意，最后一个样例不会出现在 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 翻译