Thuận là một học sinh yêu thích nghiên cứu về số học. Một chủ đề mà Thuận đang nghiên cứu là những số mà các chữ số của nó đôi một khác nhau, ví dụ như \(0, 1, 2, 10, 102, 123, \dots\)

Để việc nghiên cứu được thuận lợi, Thuận muốn viết một chương trình nhập vào số \(X\) và trả ra kết quả là số \(Y\) mà:

• \(Y\) là một số có các chữ số đôi một khác nhau;
• \(Y > X\);
• \(Y\) nhỏ nhất có thể.

Hãy giúp Thuận viết một chương trình như thế.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu tiên gồm số nguyên \(T\) là số bộ dữ liệu (\(T \leq 50\));
• Tiếp theo là \(T\) dòng, mỗi dòng ghi một số \(X\) cần tính (\(0 \leq X \leq 10^9\)).

Output

• Ghi ra thiết bị ra chuẩn gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với bộ dữ liệu vào.

Example

3
1
10
98

2
12
102

Scoring

• Có \(50\%\) số test ứng với \(50\%\) số điểm có \(X \leq 10^6\).
• Có \(50\%\) số test còn lại ứng với \(50\%\) số điểm không có ràng buộc gì thêm.