Problem description

Student Marcin na ostatnich zajęciach Algorytmiki Olimpijskiej poznał rzymski system zapisu liczb. Niestety, nie jest fanem matematyki, dlatego postanowił używać tylko podstawowego systemu rzymskiego – takiego, w którym największą występującą cyfrą jest M, a największą liczbą jaką da się zapisać jest MMMCMXCIX.

Ponadto Marcin ma także problemy z odejmowaniem, dlatego postanowił, że w jego systemie nie będą występowały liczby, do których odczytu wymagana jest ta umiejętność. Na przykład liczba 24 w systemie rzymskim zapisywana jest jako XXIV, a aby ją odczytać potrzebujemy zsumować 10 + 10 − 1 + 5, zatem liczba ta nie występuje w systemie Marcina.

Napisz program, który wyznaczy N-tą liczbę naturalną, która nie występuje w systemie Marcina.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna N.

Wyjście

W jedynym wierszu standardowego wyjścia powinna znaleźć się N-ta liczba, której Marcin nie jest w stanie zapisać w swoim systemie.

Ograniczenia

1 ≤ N ≤ 10¹⁸.

Przykład

1

4

2

9