#!/usr/bin/env python3

def calc(n):
	a = [0]*n
	for i in range(1, n):
		a[i] = a[i-1]
		if i % 2 == 1:
			a[i] = min(a[i], a[i//2])
		if i % 3 == 2:
			a[i] = min(a[i], a[i//3])
		a[i] += 1
	return a[-1]

# def calc2(n):
# 	a = [0]*(n//2)
# 	for i in range(1, n//2):
# 		a[i] = a[i-1]
# 		if i % 2 == 1:
# 			a[i] = min(a[i], a[i//2])
# 		if i % 3 == 2:
# 			a[i] = min(a[i], a[i//3])
# 		a[i] += 1
# 	b = [min(i % 2 == 1 and a[i//2] or n, i % 3 == 2 and a[i//3] or n) for i in range(n-3, n)]
# 	return min(b[2], min(b[1], b[0] + 1) + 1) + 1

# def calcr(n):
# 	a = {1: 0}
# 	def _calc(n):
# 		if n not in a:
# 			a[n] = min(_calc(n-1), _calc(n//2) if n%2==0 else n, _calc(n//3) if n%3==0 else n) + 1
# 		return a[n]
# 	return _calc(n)

def calcr2(n):	### O(log(n)^2) (?)
	a = {0: 0, 1: 0}
	def _calc(n):
		if n not in a:
			a[n] = n
			for i in range(n-2, n+1):
				if i % 2 == 0: a[n] = min(a[n], _calc(i//2))
				if i % 3 == 0: a[n] = min(a[n], _calc(i//3))
				a[n] += 1
				# a[n] = min(a[n], _calc(i//2) if i%2==0 else n, _calc(i//3) if i%3==0 else n) + 1
		return a[n]
	return _calc(n)
	# r = _calc(n)
	# from math import log
	# print(len(a)/log(n, 2)**2)
	# return r

for i in range(1, 100):
	assert calc(i) == calcr2(i)

# print(calc2(10))
# print(calcr2(110452311))
print(calcr2(110452311110452311110452311110452311110452311110452311))
# calcr2(110452311)
# calcr2(110452311110452311110452311)
# calcr2(110452311110452311110452311110452311110452311110452311)
# calcr2(110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311)
# calcr2(110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311110452311)
# print(calc(1104523))