Số đẹp

Trên thế giới có nhiều dân tộc, mỗi dân tộc có nền văn hóa của riêng họ. Dân tộc X có quan niệm về số đẹp và họ rất coi trọng số đẹp. Số đẹp của họ là số chỉ chứa chữ số \(5\) và chữ số \(8\). Được qui ước như sau: số đẹp thứ nhất là \(5\), số đẹp thứ hai là \(8\), số đẹp thứ ba là \(55\), số đẹp thứ tư là \(58\), số đẹp thứ năm là \(85\), số đẹp thứ sáu là \(88\), ..., số đẹp thứ mười là \(588\), ...

Yêu cầu: Hãy tìm số đẹp thứ \(K\).

Input

Dữ liệu vào gồm: duy nhất số \(K\) (\(1 \le K \le 10^{18}\)).

Ràng buộc:

• Có \(60\%\) số test \(1 \le K \le 10^8\).

• Có \(40\%\) số test không ràng buộc gì thêm.

Output

In ra trên một dòng: số đẹp thứ \(K\) tìm được.

Example

Input:

10

Output:

588