Background

Special for beginners, ^_^

Description

十进制数字中，只含有 6 与 ８ 的数字被称作幸运数。将所有的幸运数从小到大排序，第一个幸运数是 6，接下来是 8,66,68,86,88, …

给定 $n$，请输出第 $n$ 个幸运数。

Format

Input

单个整数：表示 $n$。

Output

单个整数：表示第 $n$ 个幸运数。

Samples

7

666

Limitation

1s, 1024KiB for each test case.

$30\%$ 的数据，$1≤n≤500$

$60\%$ 的数据，$1≤n≤1,000,000$

$100\%$ 的数据，$1≤n≤1,000,000,000,000,000$