На лист хартија Петре почнал да ги пишува броевите почнувајќи од бројот еден, па два итн. Но тој ги изоставувал броевите во кои има две соседни, а исти цифри (како на пример броевите 22, 77, 133, 222, 1224...)

За даден цел број K, да се определи кој е K-тиот број кој го напишал Петре.

Влез

Во првиот и единствен ред се внесува еден цел број K кој го означува редниот број на бројот кој го напишал Петре.

Забелешка:

Во 20% од тест случаите ќе важи дека 1<= K <=1 000 000.

Во 50% од тест случаите ќе важи дека 1<= K <=10^20.

Во 100% од тест случаите ќе важи дека 1<= K <=10^100.

Излез

Се печати K-тиот број кој го напишал Петре.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
1

излез
1

влез
10

излез
10

влез
11

излез
12

Објаснување за првиот тест пример: Првиот број е 1.

Објаснување за вториот тест пример: Десеттиот број е 10.

Објаснување за третиот тест пример: Единаесеттиот број е 12. Петре не го запишал бројот 11 затоа што содржи две исти соседни цифри.