给定一个由 $k$ 位十进制数字组成的且无前导零的正整数 $M$，对 $M$ 进行“数字循环移位”是指将 $M$ 的前 $j$ 位与剩余的 $(k - j)$ 位进行交换所生成的数，其中 $0 \le j < k$。例如，231 和 312 都是 123 的数字循环移位，而 321 和 132 则不是。

如果一个正整数 $G$ 的任意数字循环移位都不超过 $G$，则称 $G$ 为“好数”。

给定一个正整数 $N$，求不超过 $N$ 的最大好数。

输入格式

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

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是不超过 $N$ 的最大好数。

数据范围

• $1 \le T \le 500$。
• $1 \le N \le 10^{10000000}$。
• $1 \le |N| \le 3 \times 10^7$。

样例

样例输入 1

4
110
10010
45363
8394634

样例输出 1

Case #1: 110
Case #2: 10000
Case #3: 44444
Case #4: 8383837

说明

在第一个样例中，110 是一个好数，因为它的所有数字循环移位 101 和 011 都小于 110。

在第二个样例中，10010 本身不是一个好数，因为它的一个数字循环移位 10100 大于 10010。10001 到 10009 也不是，因为 10001 的循环移位是 11000，10009 的循环移位是 91000，10002 到 10008 的情况类似。因此，10000 是最大的好数。