To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:

* 1 yen (the currency of Japan)

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

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




At least how many operations are required to withdraw exactly N yen in total?

It is not allowed to re-deposit the money you withdrew.

Constraints

* 1 \leq N \leq 100000
* N is an integer.

Input

Input is given from Standard Input in the following format:


N


Output

If at least x operations are required to withdraw exactly N yen in total, print x.

Examples

Input

127


Output

4


Input

3


Output

3


Input

44852


Output

16
import copy
N=input()

def nine(m):
	if m<9: return m
	for i in range(1000):
		t=9**i
		if t>m:
			t1=9**(i-1)
			return m-t1
def six(m):
	if m<6: return m
	for i in range(1000):
		t=6**i
		if t>m:
			t2=6**(i-1)
			return m-t2


Z=15
k=1<<Z

b=set()
for i in range(k):

	n=copy.deepcopy(N)
	ans=0
	for j in range(Z):
		if n<6:
			b.add(ans+n)
			break
		if i&(1<<j)!=0:
			#9
			n=nine(n)
			ans+=1
		else:
			#6
			n=six(n)
			ans+=1


print min(b)


