Số chẵn lẻ đan xen là số nguyên dương mà hai chữ số liên tiếp trong số đó không cùng tính chẵn hoặc không cùng tính lẻ.

Ví dụ: 1236, 258, 123698, ... là các số chẵn lẻ đan xen.

Yêu cầu: Cho biết số chẵn lẻ đan xen thứ \(n\).

Input

• Một số nguyên dương \(n\).

Output

• In ra số chẵn lẻ đan xen thứ \(n\).

Constraints

• \(1 \le n \le 10^{15}\).

Example

1

1

100

290