You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

输入一个不超过100,000位的16进制数，请转换成8进制数。

注：16进制数中，字母0-9还对应表示数字0-9，字母"A"（大写）表示10，"B"表示11,..."F"表示15. 比如：16进制数A10B表示的10进制数是：1016^3 + 116^2 + 016^1 + 1116^0 = 41227. 转换成的8进制数是： 120413 ：因为 18^5 + 28^4 + 08^3 + 48^2 + 18^1 + 38^0 = 41227.

提示：考虑它们与2进制表示的关系。

Input Format

一行，一个16进制数。没有前导0（除非是数字0）

Output Format

一个8进制数。没有前导0（除非是数字0）

Sample

input

123ABC

output

4435274

Hint

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$