Hàm rev(x) được xác định bằng cách đảo ngược thứ tự viết các chữ số trong x.

Cho dãy số nguyên a₁,a₂,a₃,...,a_n được xác định như sau:

- a₁ = 1

- a_n = rev(a_n-1) + 2

Bảng dưới đây cho biết một số giá trị đầu tiên của dãy a

Yêu cầu

- Cho số nguyên dương n, xác định a_n

Input

- Số nguyên dương n (1<=n<=10¹²)

Output

- Số a_n