Ever wonder what will happen when you meet a person who uses a different base system to talk about numbers? For example, when you hear someone saying this mysterious number 1010110001 (which is in binary), can you quickly convert it to its decimal form, 689?

In Harkerland, everyone uses the octal numeral system (base $8$) when talking about numbers. Therefore, new immigrants often have difficulties parsing numbers quickly. One of them is Alex. Alex used to live in a place where the hexadecimal numeral system (base $16$) is adopted. In order to adapt to the Harkerland lifestyle as soon as possible, he trains hard to perform fast octal-to-hexadecimal conversion. Before Alex’s training finishes, he is going to rely on a program for the base conversion. Help Alex write such a program.

Use capital letters A, B, $\dots $, F to represent the values $10, 11, \ldots , 15$ in hexadecimal.

-----Input-----
The only line of input consists of a non-negative integer, written in base $8$. The given integer will have no leading zeroes and will be strictly smaller than $8^{200000}$.

-----Output-----
Output the same integer, written in base $16$. The output must not include any extra leading zeroes.

-----Explanation for sample data-----
For Sample Input 1, $4444_8 = 2340_{10} = 924_{16}$.

-----Examples-----
Sample Input 1:
4444
Sample Output 1:
924

Sample Input 2:
20
Sample Output 2:
10

Sample Input 3:
3211
Sample Output 3:
689

Difficulty: interview

Starter code:

Solutions: