Cho số nguyên dương ~n~.

Mỗi bước, bạn có thể thực hiện một trong ba thao tác sau:

• Trừ ~1~.
• Chia cho ~2~ (nếu ~n~ chia hết cho ~2~).
• Chia cho ~3~ (nếu ~n~ chia hết cho ~3~).

Yêu cầu: Tính và in ra số bước tối thiểu cần thực hiện để biến ~n~ thành ~1~ bằng các thao tác đã cho.

Input

Một số nguyên dương ~n~ (~1 \leq n \leq 10^6~).

Output

Một số nguyên - là số bước ít nhất cần để đưa ~n~ về ~1~.

Example input 1

10

Example output 1

3

Note 1

• Các bước tối ưu: ~10 → 9 → 3 → 1~ (3 bước).