Tatiana 喜欢保持事物整洁。她的玩具按从小到大排序，铅笔按从短到长排序，电脑按从旧到新排序。有一天，在练习数数时，她注意到一些整数在十进制表示下（无前导零）其数字呈非递减顺序排列。例如 8、123、555 和 224488。她决定将这些数字称为“整洁数”（tidy numbers）。而不具备此性质的数字，如 20、321、495 和 999990，则不是整洁数。

她刚刚完成了从 1 到 $N$ 的所有正整数的升序计数。请问她数出的最后一个整洁数是多少？

输入格式

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

输出格式

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

数据范围

$1 \le T \le 100$。

小数据规模（测试点 1 - 可见）

$1 \le N \le 1000$。

大数据规模（测试点 2 - 隐藏）

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

样例

输入格式 1

4
132
1000
7
111111111111111110

输出格式 1

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

说明

注意，最后一个样例不会出现在小型数据集中。