Депутатські щасливі числа

Limits: 2 sec., 256 MiB

Кожен громадянин знає, що щасливим числом є те, десятковий запис якого містить тільки четвірки та сімки. Наприклад, щасливими є числа 4, 7, 47, 7777 та 4744474.

Проте депутати — люди непересічні і їм завжди потрібно щось інакше, щось краще, щось більш вишукане чи елегантне. Вони їздять на інакших авто, вони живуть у інакших будинках. Дехто вірить, що їх навіть інопланетяни інакші викрадають.

Ця хвороблива депутатська схильність не оминула і щасливих чисел. Тож депутатським щасливим числом є таке щасливе число, у десятковому записі якого цифри змінюються щасливу кількість разів. Наприклад, депутатськими щасливими числами є 47474 та 7777477744447474, а числа 47, 47747447744777744474744774 такими не є. Число 47474 має 4 зміни цифр, число 77744 — одну зміну, а число 44444444 — жодної.

Розглянемо всі депутатські щасливі числа у порядку зростання. Ваше завдання — відшукати \(n\)-те щасливе депутатське число.

Input

У єдиному рядку задано одне ціле число \(n\) — номер шуканого депутатського щасливого числа.

Output

У єдиному рядку виведіть одне ціле число — \(n\)-те депутатське щасливе число.

Constraints

\(1 \le n \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7	477474

Notes

Перші 7 депутатських щасливих чисел:

47474, 74747, 447474, 474474, 474744, 474774, 477474.