Problem description

Czarnoksiężniczka Anna ostatnio kupiła siedmiosegmentowy wyświetlacz o nieskończenie wielu cyfrach do pokazywania liczby zaklęć, które umie już rzucić. Czarnoksiężniczka Anna jest oszczędna, dlatego chciałaby, żeby w jej wyświetlaczu było włączonych jak najmniej segmentów.

Chwilę pomyślała i zdefiniowała na dodatnich liczbach całkowitych Nowy Porządek Anny: niech f(n) oznacza liczbę włączonych segmentów w reprezentacji liczby n na wyświetlaczu siedmiosegmentowym. Wówczas x<_Ay wtedy i tylko wtedy, gdy f(x) < f(y) lub, jeżeli f(x) i f(y) są równe, zachodzi nierówność x < y.

Anna potrafi rzucić już N zaklęć. Jaką liczbę pokazuje jej wyświetlacz?

Napisz program, który wczyta liczbę N, wyznaczy N-tą z kolei liczbę w porządku <_A i wypisze ją na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna dodatnia liczba całkowita N oznaczająca liczbę zaklęć, które umie rzucić Czarnoksiężniczka Anna.

Wyjście

W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną dodatnią liczbę całkowitą – zawartość wyświetlacza Czarnoksiężniczki Anny.

Ograniczenia

1 ≤ N ≤ 10¹⁵.

Przykład

12

14

15

111