Số đối xứng là số mà viết các chữ số của nó theo chiều từ trái sang phải hay từ phải sang trái đều là số đó.

Số đối xứng dạng nón là số đối xứng mà các chữ số tăng dần từ trái đến giữa và từ phải đến giữa.

Ví dụ, các số \(11,13631,245542,1357531,24688642,...\) là các số đối xứng dạng nón, còn các số \(23332,245642\) không phải số đối xứng dạng nón.

Yêu cầu: Đưa ra số đối xứng dạng nón từ \(1\) đến \(N\).

Input

• Nhập vào duy nhất một số tự nhiên \(N\) (\(N \le 10^{10}\)).

Output

• Đưa ra kết quả bài toán.

Scoring

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

Example

123

19