Người Á Đông quan niệm số gồm các chữ số ~6~ và ~8~ là chữ số may mắn. Nhân dịp năm mới giáp thìn ~(2024)~ một nhóm học sinh đến chúc tết thầy và được mừng tuổi cho các học sinh của mình với số tiền là một số tự nhiên nhỏ nhất chỉ gồm các chữ số ~6~ và ~8~ chia hết cho tích số tuổi của các học sinhn.

Input

Một số nguyên dương ~n~ là tích số tuổi của nhóm sinh viên ~(17 \le n \le 10^6)~.

Output

Nếu tìm được số nguyên dương nhỏ nhất chia hết cho ~n~ chỉ gồm các chữ số ~6~ và ~8~ thì xuất ra số tiền mừng tuổi tương ứng với số đó, trong trường hợp không có số nào thỏa mãn xuất ra số ~0.~

Example 1

Input

20

Output

0

Example 2

Input

123456

Output

686688888866688