Problem Statement

Việc rút tiền là một việc khó khăn, vì vậy một ngân hàng đã quyết định chỉ cho khách hàng với các mệnh giá sau:

• ~1~ yen (Đơn vị tiền của Nhật)

• ~6~ yen, ~6^2(=36)~ yen, ~6^3(=216)~ yen, ...

• ~9~ yen, ~9^2(=81)~ yen, ~9^3(=729)~ yen, ...

Một vị khách đang cần đi vội, hỏi vị khách này cần rút ít nhất bao nhiều lần để được ~N~ yen tổng cộng?

Không được phép đổi lại số tiền bạn đã rút.

Constraints

• ~1 \leq N \leq 100000~
• ~N~ is an integer.

Input

Đầu vào được cung cấp từ Đầu vào chuẩn ở định dạng sau:

~N~

Output

Số lần rút ít nhất để được N yen

Sample Input 1

127

Sample Output 1

4

Số tiền rút như sau ~1~ yen, ~9~ yen, ~36(=6^2)~ yen and ~81(=9^2)~ yen, chúng ta sẽ có được ~127~ yen sau 4 lần rút.

Sample Input 2

3

Sample Output 2

3

Sample Input 3

44852

Sample Output 3

16