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ố là các chữ số của nó đôi một khác nhau, ví dụ như \(0,1,2,10,102,123,...\)

Để việc nghiên cứu 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

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

Output

• Gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với bộ dữ liệu vào.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(X \le 10^6\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

3
1
10
98

2
12
102