程序设计能力实训

1112. 找数

单点时限: 2.0 sec

内存限制: 256 MB

“非下降数”表示一个整数的高位数码不会大于低位数码。

11123345,111是“非下降数”,121,11123343不是“非下降数”。

现在给定一个整数 $n$ $(1 \leq n \leq 10^{18})$,找出不大于 $n$ 的最大“非下降数”。

输入格式

第 $1$ 行:整数T(1≤T≤100)为问题数。

第2行:第一个问题的数据$n$。

第3∽T+1行:后面问题的数据,格式与第一个问题相同。

输出格式

对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0: 等),然后在每一行中输出找到的那个数。

样例

Input
3
1
1000
111111111111111110
Output
case #0:
1
case #1:
999
case #2:
99999999999999999
不限期开放

题目列表