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

Cho dãy số nguyên \(a_1,a_2,...,a_n\), ta sắp xếp lại dãy thành dãy không tăng bằng các bước như sau:

• Tìm số \(i\) nhỏ nhất thỏa mãn tồn tại số \(j\) sao cho \(i < j\) và \(a_i < a_j\).
• Nếu tồn tại số \(i\) như vậy, chuyển số \(a_i\) về cuối dãy.
• Nếu không tồn tại số \(i\) như vậy, kết thúc chương trình.

Yêu cầu: Cho dãy số nguyên ban đầu, hãy tính số bước cần thực hiện.

Input

• Dòng đầu gồm số nguyên \(n\) (\(1 \le n \le 3 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(a_i \le 10^9\)).

Output

• Một số duy nhất là số bước cần thực hiện.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 500\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(a_i \le 3\).
• Subtask \(4\) (\(20\%\) số điểm): \(a_1 \le a_2 \le ... \le a_n\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

6
2 4 3 1 2 3

4

Cho một đa giác lồi có \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\). Người ta chia đa giác này thành \(m+1\) đa giác con bằng \(m\) đường chéo (\(m \le n-3\)). Các đường chéo này cùng với \(n\) cạnh của đa giác đôi một không trùng nhau hay cắt nhau (chỉ có điểm chung tại các đầu mút). Một đa giác con gồm các đỉnh lần lượt \(x_1,x_2,...,x_t\) được coi là có giá trị \(\Sigma_{i=1}^t 2^{x_i}\).

Cho đa giác, \(m\) đường chéo và số nguyên dương \(k\) (\(k \le m+1\)), sắp xếp các đa giác con theo giá trị tăng dần, hãy xác định đa giác con thứ \(k\).

Input

• Dòng đầu gồm ba số nguyên \(n,m,k\) (\(3 \le n \le 5 \times 10^5, 0 \le m \le n-3, 1 \le k \le m+1\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) (\(1 \le u,v \le n\)) thể hiện một đường chéo trong đa giác.

Output

• Một dòng chứa các đỉnh của đa giác con thứ \(k\) (các đỉnh được ghi theo thứ tự tăng dần).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 50, m \le 20\).
• Subtask \(2\) (\(25\%\) số điểm): \(m = 1\).
• Subtask \(3\) (\(25\%\) số điểm): \(m = n-3\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

6 3 2
1 3
1 4
1 5

1 3 4