Cho số tự nhiên ~a~, hãy tìm số tự nhiên ~x~ thỏa mãn hai điều kiện:

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

Yêu cầu: Tìm số tự nhiên ~x~ lớn nhất thỏa mãn các điều kiện trên.

Input

• Dòng 1: Chứa số nguyên dương ~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~ ứng với một test (~0 \le a \le 10^9~).

Output

• Ghi ra ~T~ dòng, mỗi dòng ghi kết quả là số ~x~ tìm được với test tương ứng.

Sample Input 1

8
0
11
1000
5678
3498
135246
345341
123456788

Sample Output 1

0
9
789
5678
3489
134789
256789
23456789