Tìm số

Cho số tự nhiên \(a\). Hãy tìm số tự nhiên \(x\) thỏa mãn các điều kiện sau:

• \(x \le a\);
• Biểu diễn thập phân của \(x\) gồm các chữ số tăng nghiêm ngặt từ trái qua phải (từ hàng cao nhất đến hàng đơn vị). Nếu \(x\) chỉ có một chữ số thì cũng được coi là thỏa mãn.

Input

• Dòng đầu chứa số nguyên dương \(T\) \((T \le 10^6)\) là số test.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số tự nhiên \(a\) \((0 \le a \le 10^9)\).

Output

• Ghi ra \(T\) dòng, mỗi dòng là số \(x\) lớn nhất thỏa mãn yêu cầu tương ứng với test đó.

Scoring

• Subtask 1 (40%): \(T \le 10\) và \(a \le 10^6\).
• Subtask 2 (30%): \(a \le 10^6\).
• Subtask 3 (20%): \(T \le 100\).
• Subtask 4 (10%): Không có ràng buộc gì thêm.

Sample Input 1

8
0
11
1000
5678
3498
135246
345341
123456788

Sample Output 1

0
9
789
5678
3489
134789
256789
23456789