题目描述
一个数字可以被分成两部分（可能有一部分是空的），前半部分属于非递减，后半部分属于非递增。
例如 12321、12345、54321、12333、32111 都是升降数字。
现在给定数字n，请求出不超过n的最大的升降数字。

输入格式
输入第一行为正整数T，表示存在T组测试数据。
每组测试数据输入一行，包含一个数字 n 。

数据范围
1 ≤ T ≤ 1000
1 ≤ n < 10^100000

输出格式
对于每组测试数据输出一个数字表示答案。

样例

5
29041
56577
12345
54300
135341

29000
56555
12345
54300
135333