Bessie was teaching Jessie, her protege interesting in programming contests the binary facts of life. She explained that computers work in binary (base 2) and that all computer numbers in general are stored as 0's and 1's. Jessie was a bit unclear on the concept, so Bessie made her an exercise, shown below.</p>

Write a program that converts an unsigned hexadecimal number to octal (base 8) form.  Hexadecimal number can have at most 100,000 digits and is composed of digits and capital letters from A to F.

Note: a hexadecimal number is a special way of representing numbers in base 16. The digits 0-9 still correspond to 0-9, and then A (capital A!) corresponds to 10, B to 11, etc. (F stands for 15).

For example, the hexadecimal number A10B corresponds to the (decimal) number 1016^3 + 116^2 + 016^1 + 1116^0 = 41227. The corresponding octal (base 8) number would be 120413, since 18^5 + 28^4 + 08^3 + 48^2 + 18^1 + 38^0 = 41227.

Hint: there is an easier way to convert from hexadecimal to octal than by converting hexadecimal -> decimal -> octal. It might help to think about the numbers in binary (base 2).

입력 형식

• Line 1: A single hexadecimal number. Multidigit numbers will have no leading zeroes (i.e., A1 instead of 00A1). 0 (by itself) is a valid input.
</ul>

 

출력 형식

• Line 1: The octal value with no leading zeros.  If the input is 0, the output should also be 0.
</ul>

 

예제 입력

123ABC

예제 출력

4435274