Xét dãy số nguyên \(a_{1},a_{2},\ldots,a_{n},\ldots\) trong đó \(a_{1} = 1\), \(a_{n}\) được xác định như sau: đảo ngược thứ tự viết các chữ số của \(a_{n - 1}\) (trong hệ cơ số 10) và cộng thêm 2 vào số nhận được.

Phần đầu của dãy số này có giá trị như sau:

Yêu cầu: Cho số nguyên dương \(n\). Hãy xác định \(a_{n}\) \((1\ \leq \ n\ \leq \ 10^{12})\).

Dữ liệu vào:

+ Gồm nhiều tests (không quá 1000), mỗi test cho trên một dòng chứa một số nguyên \(n\).

Kết quả:

+ Kết quả mỗi test đưa ra trên một dòng.

Ràng buộc:

+ Có 50% số test có \(n \leq 10^{5}\)

+ Có 50% số test còn lại không có ràng buộc gì thêm