There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

Eat one orange.
If the number of remaining oranges (n) is divisible by 2 then you can eat  n/2 oranges.
If the number of remaining oranges (n) is divisible by 3 then you can eat  2*(n/3) oranges.

You can only choose one of the actions per day.
Return the minimum number of days to eat n oranges.
 
Example 1:
Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

Example 2:
Input: n = 6
Output: 3
Explanation: You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.

Example 3:
Input: n = 1
Output: 1

Example 4:
Input: n = 56
Output: 6

 
Constraints:

1 <= n <= 2*10^9

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: class Solution:
    def minDays(self, n: int) -> int:
        

Solutions:
import functools

class Solution:

	@functools.lru_cache()
	def minDays(self, n: int) -> int:
		if n <= 1:
			return n
		return 1 + min(n % 2 + self.minDays(n // 2), n % 3 + self.minDays(n // 3))


memo = {}
f = min

class Solution:

	def minDays(self, n: int) -> int:
		if n < 2:
			return n
		if n in memo:
			return memo[n]
		a = 1 + f(self.minDays(n // 2) + n % 2, self.minDays(n // 3) + n % 3)
		memo[n] = a
		return a


class Solution:

	def minDays(self, n: int) -> int:

		@lru_cache(None)
		def dp(m):
			if m == 0:
				return 0
			if m == 1:
				return 1
			return 1 + min(m % 2 + dp(m // 2), m % 3 + dp(m // 3))
		return dp(n)


class Solution:

	def minDays(self, n: int) -> int:
		ONE_LIMIT = 50
		TWO_LIMIT = 23
		f = {1: 1}

		def search(n, one, two):
			if one > ONE_LIMIT:
				return 1000
			if two > TWO_LIMIT:
				return 1000
			if n in f:
				return f[n]
			ans = 1000
			if n % 3 == 0:
				ans = min(ans, search(n // 3, one, two))
			if n % 2 == 0:
				ans = min(ans, search(n // 2, one, two + 1))
			ans = min(ans, search(n - 1, one + 1, two))
			f[n] = 1 + ans
			return f[n]
		search(n, 0, 0)
		return f[n]


class Solution:

	def minDays(self, n: int) -> int:

		def t(n):
			stack = {n}
			ct = 0
			while stack:
				tmp = set()
				for i in stack:
					if i == 0:
						return ct
					if i % 2 == 0:
						tmp.add(i // 2)
					if i % 3 == 0:
						tmp.add(i // 3)
					tmp.add(i - 1)
				ct += 1
				stack = tmp
		return t(n)


class Solution:

	def minDays(self, n: int) -> int:
		dp = [0] * 1000
		for i in range(1, 1000):
			dp[i] = dp[i - 1] + 1
			if i % 2 == 0:
				dp[i] = min(dp[i // 2] + 1, dp[i])
			if i % 3 == 0:
				dp[i] = min(dp[i // 3] + 1, dp[i])
		d = {}
		d[0] = 0
		d[1] = 1

		def cal(k):
			if k in d:
				return d[k]
			a = k
			a = min(a, cal(k // 3) + k % 3 + 1)
			a = min(a, cal(k // 2) + k % 2 + 1)
			d[k] = a
			return d[k]
		for i in range(1, 999):
			if dp[i] != cal(i):
				print((i, dp[i], cal(i)))
		return cal(n)


class Solution:

	def minDays(self, n: int) -> int:
		if n == 0:
			return 0
		current = set([n])
		level = 0
		while True:
			level += 1
			temp = set()
			for num in current:
				if num == 1:
					return level
				if num % 2 == 0:
					temp.add(num // 2)
				if num % 3 == 0:
					temp.add(num // 3)
				temp.add(num - 1)
			current = temp


class Solution:

	def mp_gen(self):
		dp = [[0] * 32 for _ in range(32)]
		dp[0][0] = 1
		mp = {}
		for i in range(32):
			for j in range(32):
				k = 2 ** i * 3 ** j
				if i == 0 and j == 0:
					dp[i][j] = 1
				elif i == 0:
					dp[i][j] = dp[i][j - 1] + 1
				elif j == 0:
					dp[i][j] = dp[i - 1][j] + 1
				else:
					dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
				mp[k] = dp[i][j]
		return mp

	def minDays(self, n: int) -> int:
		if n == 1:
			return 1
		cnt = 0
		st = set()
		st.add(n)
		while st:
			cnt += 1
			st_temp = set()
			for v in st:
				if v == 1:
					return cnt
				st_temp.add(v - 1)
				if v % 2 == 0:
					st_temp.add(v // 2)
				if v % 3 == 0:
					st_temp.add(v // 3)
			st = st_temp
		return -1


from collections import deque

class Solution:

	def minDays(self, n: int) -> int:
		q = deque([n])
		days = 0
		visited = set()
		while q:
			days += 1
			for _ in range(len(q)):
				node = q.popleft()
				if node == 1:
					print(visited)
					return days
				if node % 3 == 0 and node % 3 not in visited:
					q.append(node // 3)
					visited.add(node // 3)
				if node % 2 == 0 and node % 2 not in visited:
					q.append(node // 2)
					visited.add(node // 2)
				if node - 1 not in visited:
					q.append(node - 1)
					visited.add(node - 1)


class Solution:

	def minDays(self, n: int) -> int:
		queue = collections.deque()
		queue.append(n)
		level = 0
		while queue:
			subList = set()
			for i in range(len(queue)):
				oranges = queue.popleft()
				subList.add(oranges - 1)
				if oranges % 2 == 0:
					subList.add(oranges - oranges // 2)
				if oranges % 3 == 0:
					subList.add(oranges - 2 * (oranges // 3))
			level += 1
			if 0 in subList:
				return level
			for val in subList:
				queue.append(val)


class Solution:

	def minDays(self, n: int) -> int:
		i = 1
		c_set = {n}
		while 1 not in c_set:
			new_set = set()
			for a in c_set:
				new_set.add(a - 1)
				if a % 2 == 0:
					new_set.add(a // 2)
				if a % 3 == 0:
					new_set.add(a // 3)
			c_set = new_set
			i += 1
		return i


class Solution:

	def helper(self, n):
		if n in self.dp:
			return self.dp[n]
		if n < 0:
			return float('inf')
		elif n == 0:
			return 0
		ret = self.helper(n - 1)
		if n % 3 == 0:
			ret = min(ret, self.helper(n - 2 * (n // 3)))
		if n % 2 == 0:
			ret = min(ret, self.helper(n // 2))
		self.dp[n] = 1 + ret
		return self.dp[n]

	def minDays(self, n: int) -> int:
		q = [n]
		step = 0
		while q:
			nxts = set()
			for nn in q:
				if nn == 0:
					return step
				nxts.add(nn - 1)
				if nn % 2 == 0:
					nxts.add(nn // 2)
				if nn % 3 == 0:
					nxts.add(nn - 2 * (nn // 3))
			step += 1
			q = deque(nxts)


class Solution:

	def minDays(self, n: int) -> int:
		q = set([n])
		level = 1
		while q:
			new_q = set()
			for node in q:
				if node - 1 == 0:
					return level
				new_q.add(node - 1)
				if node % 2 == 0:
					new_q.add(node // 2)
				if node % 3 == 0:
					new_q.add(node // 3)
			level += 1
			q = new_q


class Solution:

	def minDays(self, n: int) -> int:
		(frontier, res) = ([n], 0)
		while frontier:
			new_frontier = set()
			for el in frontier:
				if el == 1:
					return res + 1
				new_frontier.add(el - 1)
				if el % 2 == 0:
					new_frontier.add(el // 2)
				if el % 3 == 0:
					new_frontier.add(el // 3)
			res += 1
			frontier = list(new_frontier)


from queue import Queue

class Solution:

	def minDays(self, n: int) -> int:
		q = Queue()
		q.put(n)
		vis = set()
		vis.add(n)
		ans = 1
		while True:
			sz = q.qsize()
			for rep in range(sz):
				u = q.get()
				if u == 1:
					return ans
				if u - 1 not in vis:
					vis.add(u - 1)
					q.put(u - 1)
				if u % 2 == 0 and u // 2 not in vis:
					vis.add(u // 2)
					q.put(u // 2)
				if u % 3 == 0 and u // 3 not in vis:
					vis.add(u // 3)
					q.put(u // 3)
			ans += 1
		return -1


class Solution:

	def minDays(self, n: int) -> int:
		s = {n}
		step = 0
		while s:
			ns = set()
			for curr in s:
				if curr == 0:
					return step
				if curr - 1 not in s:
					ns.add(curr - 1)
				if curr % 2 == 0 and curr // 2 not in s:
					ns.add(curr // 2)
				if curr % 3 == 0 and curr // 3 not in s:
					ns.add(curr // 3)
			step += 1
			s = ns
		return step


from math import log, ceil

class Solution:

	def minDays(self, n: int) -> int:

		def one_day(apples):
			if apples % 2 == 0 and apples % 3 != 0:
				return (apples / 2, apples - 1)
			elif apples % 3 == 0 and apples % 2 != 0:
				return (apples / 3, apples - 1)
			elif apples % 3 == 0 and apples % 2 == 0:
				return (apples / 3, apples / 2)
			elif apples % 3 != 0 and apples % 2 != 0:
				return (apples - 1,)
		poses = [(n, 0)]
		min_apples = min([pos[0] for pos in poses])
		while min_apples != 0:
			new_poses = []
			for pos in poses:
				apples = pos[0]
				days = pos[1]
				new_pos = [(new_apples, days + 1) for new_apples in one_day(apples)]
				if min([pos[0] for pos in new_pos]) == 0:
					return sorted(new_pos, key=lambda x: x[0])[0][1]
				new_poses += new_pos
			min_apples = min([pos[0] for pos in new_poses])
			poses = sorted(list(set(new_poses)))
		days = sorted(poses, key=lambda x: x[0])[0][1]
		return days


class Solution:

	def minDays(self, n: int) -> int:
		days = 0
		s0 = set()
		s1 = set()
		s1.add(n)
		while True:
			days += 1
			for si in s1:
				if si == 1:
					return days
				if si % 2 == 0:
					s0.add(si // 2)
				if si % 3 == 0:
					s0.add(si - 2 * (si / 3))
				s0.add(si - 1)
			s1 = s0
			s0 = set()


class Solution:

	def minDays(self, n: int) -> int:

		@lru_cache(None)
		def eat(remaining, day):
			if remaining == 0:
				return day
			e_3 = eat(remaining - 2 * (remaining // 3), day + 1) if remaining % 3 == 0 else eat(remaining - remaining % 3, day + remaining % 3)
			e_2 = eat(remaining - remaining // 2, day + 1) if remaining % 2 == 0 else eat(remaining - 1, day + 1)
			return min(e_3, e_2)
		return eat(n, 0)


from queue import Queue

class Solution:

	def minDays(self, n: int) -> int:
		q = Queue()
		seen = set()
		q.put((n, 0))
		seen.add(n)
		while not q.empty():
			(cur, days) = q.get()
			if cur == 1:
				return days + 1
			q.put((cur - 1, days + 1))
			seen.add(cur - 1)
			if cur % 2 == 0 and cur // 2 not in seen:
				q.put((cur // 2, days + 1))
				seen.add(cur // 2)
			if cur % 3 == 0 and cur // 3 not in seen:
				q.put((cur // 3, days + 1))
				seen.add(cur // 3)


class Solution:

	def minDays(self, n: int) -> int:
		dp = [n, n, n]
		last = set([n])

		def min_2(nums):
			xs = [x for x in nums if x % 2 == 0]
			if not xs:
				return min(nums)
			return min(xs) // 2

		def min_3(nums):
			xs = [x for x in nums if x % 3 == 0]
			if not xs:
				return min(nums)
			return min(xs) // 3
		for i in range(1, n + 1):
			curr = set()
			for n in last:
				curr.add(n - 1)
			for n in last:
				if n % 2 == 0:
					curr.add(n // 2)
			for n in last:
				if n % 3 == 0:
					curr.add(n // 3)
			last = last | curr
			if any((n == 0 for n in last)):
				return i
		return n


class Solution:

	def minDays(self, n: int) -> int:
		last = {n}
		cnt = 0
		while 1:
			neo = set()
			for i in last:
				if i == 0:
					return cnt
				neo.add(i - 1)
				if i % 2 == 0:
					neo.add(i // 2)
				if i % 3 == 0:
					neo.add(i // 3)
			cnt += 1
			last = neo


class Solution:

	def minDays(self, n: int) -> int:
		q = {n}
		seen = set()
		ans = 1
		while q:
			q2 = set()
			for num in q:
				if num == 1:
					return ans
				seen.add(num)
				q2.add(num - 1)
				if num % 2 == 0:
					q2.add(num // 2)
				if num % 3 == 0:
					q2.add(num // 3)
			q = q2
			ans += 1


class Solution:

	def minDays(self, n: int) -> int:
		l = {n}
		count = 0
		while not l.__contains__(0):
			count += 1
			t = set()
			for i in l:
				t.add(i - 1)
				if i % 2 == 0:
					t.add(i / 2)
				if i % 3 == 0:
					t.add(i / 3)
			l = t
		return count


class Solution:

	def minDays(self, n: int) -> int:
		mem = {1: 1}

		def calCulatedays(num):
			if not num:
				return 0
			if num in mem:
				return mem[num]
			summ = num
			oneCheck = 0
			if num % 3 == 0:
				oneCheck += 1
				summ = min(calCulatedays(num / 3), summ)
			if num % 2 == 0:
				oneCheck += 1
				summ = min(calCulatedays(num / 2), summ)
			if oneCheck != 2:
				summ = min(calCulatedays(num - 1), summ)
			mem[num] = summ + 1
			return mem[num]
		return calCulatedays(n)


class Solution:

	def minDays(self, n: int) -> int:

		@lru_cache(None)
		def days(m: int, steps: int):
			nonlocal maxSteps
			if steps >= maxSteps:
				return
			if m == 0:
				maxSteps = steps
			if m > 0:
				if m % 3 == 0:
					days(m // 3, steps + 1)
				if m % 2 == 0:
					days(m // 2, steps + 1)
				days(m - 1, steps + 1)
		maxSteps = n
		days(n, 0)
		return maxSteps


class Solution:

	def minDays(self, n: int) -> int:
		if n < 4:
			return 1 if n == 1 else 2
		(res, cur) = (0, {n})

		def Op(i):
			ans = {i - 1}
			if not i % 2:
				ans.add(i // 2)
			if not i % 3:
				ans.add(i // 3)
			return ans
		while 0 not in cur:
			cur = {x for i in cur for x in Op(i)}
			res += 1
		return res


class Solution:

	def minDays(self, n: int) -> int:
		dic = {n: 0}
		while 0 not in dic:
			tmp = {}
			for m in dic:
				tmp[m - 1] = min(dic[m - 1], dic[m] + 1) if m - 1 in dic else dic[m] + 1
				if m % 2 == 0:
					tmp[m // 2] = min(dic[m // 2], dic[m] + 1) if m // 2 in dic else dic[m] + 1
				if m % 3 == 0:
					tmp[m // 3] = min(dic[m // 3], dic[m] + 1) if m // 3 in dic else dic[m] + 1
			dic = tmp
		return dic[0]


class Solution:

	def __init__(self):
		self.dp = {}

	def dfs(self, i, count):
		if count >= 110:
			return 99999
		if i in self.dp:
			return self.dp[i]
		tmp = 90
		if i % 3 == 0:
			tmp = min(tmp, self.dfs(i // 3, count + 1))
		if tmp < 100 and i % 2 == 0:
			tmp = min(tmp, self.dfs(i // 2, count + 1))
		if tmp < 100:
			tmp = min(tmp, self.dfs(i - 1, count + 1))
		self.dp[i] = 1 + tmp
		return self.dp[i]

	def minDays(self, n: int) -> int:
		self.dp[0] = 0
		self.dp[1] = 1
		self.dp[2] = 2
		self.dp[3] = 2
		self.dp[4] = 3
		return self.dfs(n, 0)


from collections import deque

class Solution:

	def minDays(self, n: int) -> int:
		q1 = deque([0, None])
		q2 = deque([n, None])
		visited1 = {0}
		visited2 = {n}
		for i in range(n):
			while True:
				n = q1.popleft()
				if n is None:
					q1.append(None)
					break
				for m in [n + 1, n * 2, n * 3]:
					if m in visited2:
						return i * 2 + 1
					if m not in visited1:
						visited1.add(m)
						q1.append(m)
			while True:
				n = q2.popleft()
				if n is None:
					q2.append(None)
					break
				l = [n - 1]
				if n % 2 == 0:
					l.append(n // 2)
				if n % 3 == 0:
					l.append(n // 3)
				for m in l:
					if m in visited1:
						return i * 2 + 2
					if m not in visited2:
						visited2.add(m)
						q2.append(m)


class Solution:

	def minDays(self, n: int) -> int:
		(queue, steps) = ([n], 0)
		appears = dict()
		while queue:
			n_queue = []
			for ele in queue:
				appears[ele] = 1
			for ele in queue:
				if ele < 2:
					return steps + ele
				if ele - 1 not in appears:
					n_queue.append(ele - 1)
				if ele % 2 == 0 and ele / 2 not in appears:
					n_queue.append(ele // 2)
				if ele % 3 == 0 and ele / 3 not in appears:
					n_queue.append(ele // 3)
			steps += 1
			queue = n_queue
		return steps


class Solution:

	def minDays(self, n: int) -> int:
		return self.dfs(n)

	@lru_cache(None)
	def dfs(self, n):
		if n < 2:
			return n
		if n < 0:
			return -sys.maxsize
		ans = sys.maxsize
		if n % 3 == 0:
			ans = min(1 + self.dfs(n // 3), ans)
		if n % 2 == 0:
			ans = min(1 + self.dfs(n // 2), ans)
		if (n - 1) % 3 == 0 or (n - 1) % 2 == 0:
			ans = min(1 + self.dfs(n - 1), ans)
		if (n - 2) % 3 == 0:
			ans = min(2 + self.dfs(n - 2), ans)
		return ans


class Solution:

	def minDays(self, n: int) -> int:
		self.best = math.inf

		@lru_cache(None)
		def f(n, steps):
			if n == 0:
				self.best = min(self.best, steps)
				return
			if steps > self.best:
				return
			if n % 2 == 0:
				f(n // 2, steps + 1)
			if n % 3 == 0:
				f(n // 3, steps + 1)
			f(n - 1, steps + 1)
		f(n, 0)
		return self.best


class Solution:

	def minDays(self, n: int) -> int:

		def bfs(n):
			(q1, q2) = ([n], [0])
			(seen1, seen2) = ({n: 0}, {0: 0})
			(step1, step2) = (0, 0)
			while q1 or q2:
				p1 = []
				p2 = []
				step1 += 1
				step2 += 1
				while q1:
					curr1 = q1.pop()
					if curr1 in seen2:
						return seen1[curr1] + seen2[curr1]
					if curr1 % 3 == 0:
						nx = curr1 // 3
						if nx not in seen1:
							seen1[nx] = step1
							p1.append(nx)
					if curr1 % 2 == 0:
						nx = curr1 // 2
						if nx not in seen1:
							seen1[nx] = step1
							p1.append(nx)
					if curr1 - 1 not in seen1:
						seen1[curr1 - 1] = step1
						p1.append(curr1 - 1)
				while q2:
					curr2 = q2.pop()
					if curr2 in seen1:
						return seen1[curr2] + seen2[curr2]
					for nx in [curr2 * 3, curr2 * 2, curr2 + 1]:
						if nx <= n and nx not in seen2:
							seen2[nx] = step2
							p2.append(nx)
				(q1, q2) = (p1, p2)
			return -1
		return bfs(n)


from queue import Queue

class Solution:

	def minDays(self, n: int) -> int:
		q = Queue()
		q.put((n, 0))
		visited = set()
		num = n
		while num != 0:
			(num, days) = q.get()
			if num not in visited:
				visited.add(num)
				if num % 3 == 0:
					q.put((num // 3, days + 1))
				if num % 2 == 0:
					q.put((num // 2, days + 1))
				q.put((num - 1, days + 1))
		return days


class Solution:

	def minDays(self, n: int) -> int:

		@lru_cache(None)
		def eat(remaining, day):
			if remaining == 0:
				return day
			e3 = eat(remaining - 2 * remaining // 3, day + 1) if not remaining % 3 else eat(remaining - remaining % 3, day + remaining % 3)
			e2 = eat(remaining - remaining // 2, day + 1) if not remaining % 2 else eat(remaining - 1, day + 1)
			return min(e3, e2)
		return eat(n, 0)


class Solution:

	def minDays(self, n: int) -> int:
		q = [n]
		days = 1
		seen = set()
		while q:
			new_q = []
			for each in q:
				if each == 1:
					return days
				seen.add(each)
				if each % 2 == 0 and each // 2 not in seen:
					new_q.append(each // 2)
				if each % 3 == 0 and each // 3 not in seen:
					new_q.append(each // 3)
				if each - 1 not in seen:
					new_q.append(each - 1)
			q = new_q
			days += 1


class Solution:

	def minDays(self, n: int) -> int:
		dp = dict()

		def dfs(n, l):
			if l > 100:
				return sys.maxsize
			if n in dp:
				return dp[n]
			if n == 1:
				dp[n] = 1
				return dp[n]
			dp[n] = sys.maxsize
			if n % 3 == 0:
				dp[n] = min(dp[n], dfs(n // 3, l + 1) + 1)
			if n % 2 == 0:
				dp[n] = min(dp[n], dfs(n // 2, l + 1) + 1)
			dp[n] = min(dp[n], dfs(n - 1, l + 1) + 1)
			return dp[n]
		return dfs(n, 0)


class Solution:

	def minDays(self, n: int) -> int:
		m = collections.defaultdict(int)
		m[0] = 0
		m[1] = 1

		def helper(n):
			if n in m:
				return m[n]
			res = float('inf')
			if n % 3 == 0:
				res = min(res, 1 + helper(n // 3))
			if n % 2 == 0:
				res = min(res, 1 + helper(n // 2))
			if n % 3 == 1:
				res = min(res, 1 + helper(n - 1))
			if n % 3 == 2:
				res = min(res, 2 + helper(n - 2))
			if n % 2 != 0:
				res = min(res, 1 + helper(n - 1))
			m[n] = res
			return res
		return helper(n)


class Solution:

	def minDays(self, n: int) -> int:
		self.m = 10000
		self.dp = [0, 1] + [float('inf')] * (self.m - 1)
		for i in range(2, self.m + 1):
			v = []
			v.append(self.dp[i - 1])
			if i % 2 == 0:
				v.append(self.dp[i // 2])
			if i % 3 == 0:
				v.append(self.dp[i // 3])
			self.dp[i] = min(v) + 1

		def dfs(n):
			if n <= self.m:
				return self.dp[n]
			else:
				return 1 + min(n % 2 + dfs(n // 2), n % 3 + dfs(n // 3))
		return dfs(n)


class Solution:

	def minDays(self, n: int) -> int:
		q = [n]
		v = set()
		steps = 0
		while len(q) > 0:
			newq = []
			for node in q:
				if node == 0:
					return steps
				v.add(node)
				if node % 3 == 0 and node // 3 not in v:
					newq.append(node // 3)
				if node % 2 == 0 and node // 2 not in v:
					newq.append(node // 2)
				if node - 1 not in v:
					newq.append(node - 1)
			q = newq
			steps += 1
		return -1


class Solution:
	from collections import deque

	def minDays(self, n: int) -> int:
		q = deque()
		q.append(n)
		seen = set()
		ans = 1
		while q:
			new = deque()
			while q:
				k = q.popleft()
				if k == 1:
					return ans
				seen.add(k)
				if k % 3 == 0 and k // 3 not in seen:
					new.append(k // 3)
				if k % 2 == 0 and k // 2 not in seen:
					new.append(k // 2)
				if k - 1 not in seen:
					new.append(k - 1)
			q = new
			ans += 1


class Solution:

	def minDays(self, n: int) -> int:
		dp = {}
		dp[0] = 1

		def getMinDays(n, dp):
			if n == 0:
				return 0
			if n - 1 in dp:
				return dp[n - 1]
			eat2 = n % 2 + getMinDays(n // 2, dp) + 1
			eat3 = n % 3 + getMinDays(n // 3, dp) + 1
			dp[n - 1] = min(eat2, eat3)
			return dp[n - 1]
		return getMinDays(n, dp)


class Solution:

	def minDays(self, n: int) -> int:
		ans = 0
		(q1, q2) = ([n], [])
		seen = set()
		while q1:
			for u in q1:
				if u == 0:
					return ans
				seen.add(u)
				if u % 2 == 0 and u // 2 not in seen:
					q2.append(u // 2)
				if u % 3 == 0 and u // 3 not in seen:
					q2.append(u // 3)
				if u - 1 not in seen:
					q2.append(u - 1)
			(q1, q2) = (q2, [])
			ans += 1
		return ans


class Solution:

	def minDays(self, n: int) -> int:
		visited = set()
		days = -1
		q = [n]
		while q:
			days += 1
			nxt_q = []
			while q:
				cur = q.pop()
				visited.add(cur)
				if cur == 0:
					return days
				nxt_q.append(cur - 1)
				if cur % 2 == 0:
					if cur // 2 not in visited:
						nxt_q.append(cur // 2)
				if cur % 3 == 0:
					if cur // 3 not in visited:
						nxt_q.append(cur // 3)
			q = nxt_q
		return n


import functools

class Solution:

	def minDays(self, n: int) -> int:
		min_cnt = {}
		visited = set()

		@functools.lru_cache(maxsize=None)
		def dfs(num, cnt):
			visited.add(num)
			if num == 1:
				return cnt + 1
			minres = 2 * 10 ** 9
			if num in min_cnt:
				min_cnt[num] = min(min_cnt[num], cnt)
			else:
				min_cnt[num] = cnt
			if num % 3 == 0:
				minres = min(minres, dfs(num // 3, cnt + 1))
			if num % 2 == 0:
				minres = min(minres, dfs(num // 2, cnt + 1))
			if not (num + 3 in min_cnt and cnt >= min_cnt[num + 3]) or (num - 1 in min_cnt and cnt + 1 < min_cnt[num - 1]):
				minres = min(minres, dfs(num - 1, cnt + 1))
			return minres
		return dfs(n, 0)


class Solution:

	@lru_cache()
	def minDays(self, n: int) -> int:
		q = deque()
		q.append(n)
		v = set()
		ans = 0
		while len(q):
			l = len(q)
			for _ in range(l):
				x = q.popleft()
				if x - 1 == 0:
					ans = ans + 1
					return ans
				if x % 3 == 0 and x // 3 not in v:
					v.add(x)
					q.append(x // 3)
				if x % 2 == 0 and x // 2 not in v:
					v.add(x)
					q.append(x // 2)
				if x - 1 not in v:
					v.add(x)
					q.append(x - 1)
			ans += 1
		return ans


class Solution:

	def minDays(self, n: int) -> int:

		@lru_cache(None)
		def ok(n, x):
			if n == 0:
				return True
			elif x == 0:
				return False
			else:
				if n % 2 == 0 and ok(n // 2, x - 1):
					return True
				if n % 3 == 0 and ok(n - 2 * n // 3, x - 1):
					return True
				return ok(n - 1, x - 1)
		left = 0
		right = n + 1
		while right - left > 1:
			mid = (left + right) // 2
			if ok(n, mid):
				right = mid
			else:
				left = mid
		return right


class Solution:

	def minDays(self, n: int) -> int:
		if n == 1:
			return 1
		from collections import deque
		queue = deque([n])
		level = 0
		seen = set()
		while queue:
			if 0 in queue:
				break
			for _ in range(len(queue)):
				node = queue.popleft()
				if node not in seen:
					seen.add(node)
				if node % 2 == 0:
					if node - node // 2 not in seen:
						queue.append(node - node // 2)
				if node % 3 == 0:
					if node - 2 * node // 3 not in seen:
						queue.append(node - 2 * node // 3)
				if node - 1 not in seen:
					queue.append(node - 1)
			level += 1
		return level


class Solution:

	def minDays(self, n: int) -> int:
		memo = {}

		def check(num_orange, days_left):
			if days_left <= 0:
				return False
			if num_orange == 1:
				return True
			t = (num_orange, days_left)
			if t in memo:
				return memo[t]
			one = check(num_orange - 1, days_left - 1)
			two = three = False
			if num_orange % 2 == 0:
				two = check(num_orange // 2, days_left - 1)
			if num_orange % 3 == 0:
				three = check(num_orange // 3, days_left - 1)
			memo[t] = one or two or three
			return memo[t]
		for i in range(1, 50):
			if check(n, i):
				return i


class Solution:

	def minDays(self, n: int) -> int:
		days = 0
		tosee = deque([n])
		seen = set([])
		while tosee:
			s = len(tosee)
			while s:
				s -= 1
				cur = tosee.popleft()
				seen.add(cur)
				if cur == 0:
					return days
				if cur % 2 == 0 and cur // 2 not in seen:
					tosee.append(cur // 2)
				if cur % 3 == 0 and cur // 3 not in seen:
					tosee.append(cur // 3)
				if cur - 1 not in seen:
					tosee.append(cur - 1)
			days += 1
		return -1


class Solution:

	def minDays(self, n: int) -> int:
		step = 0
		seen1 = set([0])
		seen2 = set([n])
		q1 = collections.deque([0])
		q2 = collections.deque([n])
		if n == 1:
			return 1
		while q1 and q2:
			for _ in range(len(q1)):
				node = q1.popleft()
				if node in seen2:
					return step
				if node * 3 < n and node * 3 not in seen1:
					q1.append(node * 3)
					seen1.add(node * 3)
				if node * 2 < n and node * 2 not in seen1:
					q1.append(node * 2)
					seen1.add(node * 2)
				if node + 1 not in seen1:
					q1.append(node + 1)
					seen1.add(node + 1)
			step += 1
			for _ in range(len(q2)):
				node = q2.popleft()
				if node in seen1:
					return step
				if node % 3 == 0 and node // 3 not in seen2:
					q2.append(node // 3)
					seen2.add(node // 3)
				if node % 2 == 0 and node // 2 not in seen2:
					q2.append(node // 2)
					seen2.add(node // 2)
				if node - 1 not in seen2:
					q2.append(node - 1)
					seen2.add(node - 1)
			step += 1
		return -1


from collections import deque

class Solution:

	def minDays(self, n: int) -> int:

		def bfs(n, days):
			possible = -1
			q = deque([(n, 0)])
			seen = set([])
			while q:
				(left, days) = q.pop()
				if left == 0:
					return days
				seen.add(left)
				if left % 2 == 0 and left // 2 not in seen:
					q.appendleft((left // 2, days + 1))
				if left % 3 == 0 and left // 3 not in seen:
					q.appendleft((left // 3, days + 1))
				if left - 1 not in seen:
					q.appendleft((left - 1, days + 1))
		return bfs(n, 0)


class Solution:

	def minDays(self, n: int) -> int:
		import math
		ans = {}

		def dfs(n, k):
			if n in ans.keys():
				return ans[n]
			if n == 1:
				return 1
			if k > 2 * math.log(n) // math.log(2) + 100:
				return 10000000000.0
			if n == 0:
				return 0
			if n % 3 == 0:
				op3 = dfs(n // 3, k + 1) + 1
			else:
				op3 = 10000000000.0
			if n % 2 == 0:
				op2 = dfs(n // 2, k + 1) + 1
			else:
				op2 = 10000000000.0
			op1 = dfs(n - 1, k + 1) + 1
			ans[n] = min(op1, min(op2, op3))
			return ans[n]
		return dfs(n, 0)


class Solution:

	def minDays(self, n: int) -> int:
		q = [n]
		seen = set()
		res = 0
		while q:
			nq = []
			for x in q:
				if x == 0:
					return res
				cur = x
				seen.add(cur)
				if cur % 2 == 0 and cur / 2 not in seen:
					nq.append(cur / 2)
				if cur % 3 == 0 and cur / 3 not in seen:
					nq.append(cur / 3)
				if cur - 1 not in seen:
					nq.append(cur - 1)
			q = nq
			res += 1


class Solution:

	def minDays(self, n: int) -> int:
		q = collections.deque()
		q.append(n)
		lvl = 0
		seen = set()
		while q:
			size = len(q)
			for _ in range(size):
				num = q.popleft()
				if num == 0:
					return lvl
				seen.add(num)
				if num % 3 == 0 and num // 3 not in seen:
					q.append(num // 3)
				if num % 2 == 0 and num // 2 not in seen:
					q.append(num // 2)
				if num - 1 not in seen:
					q.append(num - 1)
			lvl += 1


class Solution:

	def minDays(self, n: int) -> int:
		q = collections.deque([])
		q.append((n, 0))
		seen = set()
		while q:
			(os, days) = q.popleft()
			if os == 0:
				return days
			if os % 2 == 0:
				if (os / 2, days + 1) not in seen:
					q.append((os / 2, days + 1))
					seen.add((os / 2, days + 1))
			if os % 3 == 0:
				if (os - 2 * (os / 3), days + 1) not in seen:
					q.append((os - 2 * (os / 3), days + 1))
					seen.add((os - 2 * (os / 3), days + 1))
			if (os - 1, days + 1) not in seen:
				q.append((os - 1, days + 1))
				seen.add((os - 1, days + 1))
		return days + 1 if not q else days


import sys
sys.setrecursionlimit(1500000)
from functools import lru_cache

class Solution:

	def minDays(self, n: int) -> int:

		@lru_cache(None)
		def helper(n, days, decrement=0):
			if decrement > 2:
				return math.inf
			if n == 0:
				return days
			best = 1e+100
			best = min(best, helper(n - 1, days + 1, decrement + 1))
			if n % 2 == 0:
				best = min(best, helper(n - n / 2, days + 1))
			if n % 3 == 0:
				best = min(best, helper(n - 2 * (n / 3), days + 1))
			return best
		return helper(n, 0)


class Solution:

	def minDays(self, n: int) -> int:
		queue = [[n, 0]]
		seen = set()
		for (i, d) in queue:
			if i == 0:
				return d
			seen.add(i)
			if i % 3 == 0 and i // 3 not in seen:
				queue.append([i // 3, d + 1])
			if i % 2 == 0 and i // 2 not in seen:
				queue.append([i // 2, d + 1])
			if i - 1 not in seen:
				queue.append([i - 1, d + 1])


class Solution:

	def minDays(self, n: int) -> int:

		def nex(n):
			ans = [n - 1]
			if n % 2 == 0:
				ans.append(n // 2)
			if n % 3 == 0:
				ans.append(n // 3)
			return ans
		step = 0
		states = [n]
		seen = {n}
		while True:
			states = [v for s in states for v in nex(s) if v not in seen]
			for s in states:
				seen.add(s)
			step += 1
			if 0 in seen:
				return step


class Solution:

	def minDays(self, n: int) -> int:
		(q, res, seen) = ([n], 0, set())
		while q:
			tmp = set()
			if 0 in q:
				return res
			for p in q:
				if p - 1 not in seen:
					tmp.add(p - 1)
					seen.add(p - 1)
				if p % 3 == 0 and p // 3 not in seen:
					tmp.add(p // 3)
					seen.add(p // 3)
				if p % 2 == 0 and p // 2 not in seen:
					tmp.add(p // 2)
					seen.add(p // 2)
			q = tmp
			res += 1
		return res


import math
from collections import deque

class Solution:

	def minDays(self, n: int) -> int:
		if n < 2:
			return n
		queue = deque()
		running_count = n
		min_days = 0
		queue.append((min_days, n))
		seen = set()
		while queue:
			level_len = len(queue)
			for i in range(level_len):
				(local_min, local_n) = queue.popleft()
				seen.add(local_n)
				if local_n < 0:
					continue
				if local_n == 0:
					return local_min
				if local_n % 2 == 0 and local_n - local_n // 2 not in seen:
					queue.append((local_min + 1, local_n - local_n // 2))
				if local_n % 3 == 0 and local_n - 2 * (local_n // 3) not in seen:
					queue.append((local_min + 1, local_n - 2 * (local_n // 3)))
				queue.append((local_min + 1, local_n - 1))
		return min_days


class Solution:

	def minDays(self, n: int) -> int:
		ans = 1
		queue = [n]
		seen = set()
		while queue:
			newq = []
			for x in queue:
				if x == 1:
					return ans
				seen.add(x)
				if x - 1 not in seen:
					newq.append(x - 1)
				if x % 2 == 0 and x // 2 not in seen:
					newq.append(x // 2)
				if x % 3 == 0 and x // 3 not in seen:
					newq.append(x // 3)
			ans += 1
			queue = newq


class Solution:

	def minDays(self, n: int) -> int:

		def fun(n, d):
			if n <= 1:
				return n
			if n in d:
				return d[n]
			d[n] = min(n % 2 + fun(n // 2, d), n % 3 + fun(n // 3, d)) + 1
			return d[n]
		d = {}
		return fun(n, d)


class Solution:

	def minDays(self, n: int) -> int:
		q = deque()
		q.append(n)
		days = 0
		seen = set()
		while q:
			days += 1
			for _ in range(len(q)):
				node = q.popleft()
				if node == 1:
					return days
				if node % 3 == 0 and node // 3 not in seen:
					q.append(node // 3)
					seen.add(node // 3)
				if node % 2 == 0 and node // 2 not in seen:
					q.append(node // 2)
					seen.add(node // 2)
				if node - 1 not in seen:
					q.append(node - 1)
					seen.add(node - 1)


class Solution:

	def minDays(self, n: int) -> int:
		ans = 0
		visited = set([n])
		q = collections.deque([n])
		while q:
			size = len(q)
			for _ in range(size):
				cur = q.popleft()
				if cur == 0:
					return ans
				if cur - 1 not in visited:
					visited.add(cur - 1)
					q.append(cur - 1)
				if cur % 2 == 0 and cur // 2 not in visited:
					visited.add(cur // 2)
					q.append(cur // 2)
				if cur % 3 == 0 and cur // 3 not in visited:
					visited.add(cur // 3)
					q.append(cur // 3)
			ans += 1
		return -1


class Solution:

	def minDays(self, n):
		queue = deque([n])
		visited = set()
		steps = 0
		while queue:
			q_len = len(queue)
			for _ in range(q_len):
				remain = queue.popleft()
				if remain == 0:
					return steps
				if remain - 1 not in visited:
					queue.append(remain - 1)
					visited.add(remain - 1)
				if remain // 2 > 0 and remain % 2 == 0 and (remain // 2 not in visited):
					queue.append(remain // 2)
					visited.add(remain // 2)
				if remain // 3 > 0 and remain % 3 == 0 and (remain // 3 not in visited):
					queue.append(remain // 3)
					visited.add(remain // 3)
			steps += 1
		return steps


class Solution:

	def minDays(self, n: int) -> int:
		if n <= 0:
			return 0
		q = [n]
		ans = 0
		visited = {n}
		while q:
			size = len(q)
			for _ in range(size):
				i = q.pop(0)
				if i == 1:
					return ans + 1
				if i % 3 == 0:
					next = i - 2 * i // 3
					if next not in visited:
						q.append(next)
						visited.add(next)
				if i % 2 == 0:
					next = i // 2
					if next not in visited:
						q.append(next)
						visited.add(next)
				if i - 1 not in visited:
					q.append(i - 1)
					visited.add(i - 1)
			ans += 1
		return 0


class Solution:

	def minDays(self, n: int) -> int:
		from collections import deque
		q = deque()
		q.append((n, 0))
		visited = set()
		while q:
			(new_n, days) = q.pop()
			if new_n == 0:
				return days
			if new_n in visited:
				continue
			q.appendleft((new_n - 1, days + 1))
			if new_n % 2 == 0:
				q.appendleft((new_n // 2, days + 1))
			if new_n % 3 == 0:
				q.appendleft((new_n // 3, days + 1))
			visited.add(new_n)
		return -1

	def find(self, n, memo):
		if n <= 1:
			return n
		if n in memo:
			return memo[n]
		min_val = self.find(n - 1, memo)
		if n % 2 == 0:
			min_val = min(min_val, self.find(n // 2, memo))
		if n % 3 == 0:
			min_val = min(min_val, self.find(n // 3, memo))
		memo[n] = min_val + 1
		return memo[n]


class Solution:

	def minDays(self, n: int) -> int:

		def dfs(numOrngs):
			if numOrngs in seen:
				return seen[numOrngs]
			if numOrngs == 0:
				return 0
			if numOrngs < 0:
				return float('inf')
			seen[numOrngs] = min(numOrngs % 2 + dfs(numOrngs // 2), numOrngs % 3 + dfs(numOrngs // 3)) + 1
			return seen[numOrngs]
		seen = {}
		return dfs(n) - 1


class Solution:

	def minDays(self, n: int) -> int:
		c = {n: 0}
		q = collections.deque([n])
		while 1:
			x = q.popleft()
			if x == 0:
				return c[x]
			if x % 3 == 0 and x / 3 not in c:
				c[x / 3] = c[x] + 1
				q.append(x / 3)
			if x % 2 == 0 and x / 2 not in c:
				c[x / 2] = c[x] + 1
				q.append(x / 2)
			if x - 1 not in c:
				c[x - 1] = c[x] + 1
				q.append(x - 1)


class Solution:

	def minDays(self, n: int) -> int:
		q = collections.deque([n])
		day = 0
		visited = set([n])
		while q:
			day += 1
			l = len(q)
			for i in range(l):
				tmp = q.popleft()
				if tmp - 1 not in visited:
					if tmp - 1 == 0:
						return day
					visited.add(tmp - 1)
					q.append(tmp - 1)
				if tmp % 2 == 0 and tmp / 2 not in visited:
					visited.add(tmp / 2)
					q.append(tmp / 2)
				if tmp % 3 == 0 and tmp / 3 not in visited:
					visited.add(tmp / 3)
					q.append(tmp / 3)


from collections import deque

class Solution:

	def minDays(self, n: int) -> int:
		q = deque()
		visited = set()
		q.append((n, 0))
		while len(q) > 0:
			(cur, step) = q.popleft()
			if cur in visited:
				continue
			visited.add(cur)
			if cur == 0:
				return step
			if cur % 2 == 0:
				q.append((cur // 2, step + 1))
			if cur % 3 == 0:
				q.append((cur // 3, step + 1))
			q.append((cur - 1, step + 1))
		return n


import sys
sys.setrecursionlimit(1500000)

class Solution:

	def minDays(self, n: int) -> int:

		@lru_cache(None)
		def go(x):
			if x == 0:
				return 0
			best = 1e+100
			if x % 2 == 0:
				best = min(best, go(x // 2) + 1)
			if x % 3 == 0:
				best = min(best, go(x // 3) + 1)
			if x <= 1024 or x % 2 > 0 or x % 3 > 0:
				best = min(best, go(x - 1) + 1)
			return best
		return go(n)


class Solution:

	def minDays(self, n: int) -> int:
		dq = deque([(0, n)])
		res = 0
		seen = set()
		while dq:
			(layer, num) = dq.popleft()
			if num in seen:
				continue
			else:
				seen.add(num)
			if num == 0:
				return layer
			if num % 3 == 0:
				dq.append((layer + 1, num / 3))
			if num % 2 == 0:
				dq.append((layer + 1, num / 2))
			dq.append((layer + 1, num - 1))
		return 0


class Solution:

	def minDays(self, n: int) -> int:
		res = 0
		hashmap = {}
		queue = [n]
		while queue:
			new = []
			for item in queue:
				if item in hashmap:
					continue
				if item == 0:
					return res
				if item % 2 == 0:
					new.append(item - item // 2)
				if item % 3 == 0:
					new.append(item - item // 3 * 2)
				hashmap[item] = res
				new.append(item - 1)
			res += 1
			queue = new


class Solution:

	@lru_cache()
	def minDays(self, n: int) -> int:
		x = y = z = sys.maxsize
		if n <= 1:
			return n
		if n % 2 == 0:
			x = 1 + self.minDays(n // 2)
		if n % 3 == 0:
			y = 1 + self.minDays(n // 3)
		if n % 3 != 0 or n % 2 != 0:
			z = 1 + self.minDays(n - 1)
		return min(x, y, z)


from collections import deque

class Solution:

	def minDays(self, n: int) -> int:
		d = {}
		q = deque([n])
		d[n] = 0
		while q and 0 not in d:
			item = q.popleft()
			day = d[item] + 1
			temp = [item - 1]
			if item % 2 == 0:
				temp.append(item // 2)
			if item % 3 == 0:
				temp.append(item // 3)
			for i in temp:
				if i not in d:
					d[i] = day
					q.append(i)
		return d[0]


class Solution:

	def minDays(self, N: int) -> int:

		def find_edges(x):
			edges = []
			if x - 1 >= 0:
				edges.append(x - 1)
			if x % 2 == 0:
				edges.append(x // 2)
			if x % 3 == 0:
				edges.append(x // 3)
			return edges
		q = [N]
		dist = {N: 0}
		while q:
			v = q.pop(0)
			v_edges = find_edges(v)
			for edge in v_edges:
				if not dist.get(edge, False):
					if edge == 0:
						return dist[v] + 1
					dist[edge] = dist[v] + 1
					q.append(edge)
		return dist[0]


from collections import deque

class Solution:

	def minDays(self, n: int) -> int:
		visit = {}
		q = deque()
		q.append((n, 0))
		visit[n] = True
		while q:
			(num_oranges, num_days) = q.popleft()
			if num_oranges == 0:
				return num_days
			if not num_oranges - 1 in visit:
				q.append((num_oranges - 1, num_days + 1))
				visit[num_oranges - 1] = True
			if num_oranges % 2 == 0 and (not num_oranges // 2 in visit):
				q.append((num_oranges // 2, num_days + 1))
				visit[num_oranges // 2] = True
			if num_oranges % 3 == 0 and (not num_oranges // 3 in visit):
				q.append((num_oranges // 3, num_days + 1))
				visit[num_oranges // 3] = True


from collections import deque

class Solution:

	def minDays(self, n: int) -> int:
		res = 0
		if n == 0:
			return res
		q = deque([n])
		seen = set([n])
		while q:
			res += 1
			s = len(q)
			while s > 0:
				s -= 1
				i = q.popleft()
				if i % 2 == 0:
					c = i // 2
					if not c in seen:
						seen.add(c)
						q.append(c)
				if i % 3 == 0:
					c = i // 3
					if not c in seen:
						seen.add(c)
						q.append(c)
				if i - 1 == 0:
					return res
				if not i - 1 in seen:
					seen.add(i - 1)
					q.append(i - 1)
		return -1


class Solution:

	def minDays(self, n: int) -> int:
		from collections import deque
		q = deque([(n, 1)])
		seen = set([n])
		while q:
			(node, lvl) = q.popleft()
			if node == 1:
				return lvl
			if node - 1 not in seen:
				q.append((node - 1, lvl + 1))
				seen.add(node - 1)
			if node % 2 == 0 and node // 2 not in seen:
				q.append((node // 2, lvl + 1))
				seen.add(node // 2)
			if node % 3 == 0 and node - 2 * node // 3 not in seen:
				q.append((node - 2 * node // 3, lvl + 1))
				seen.add(node - 2 * node // 3)


class Solution:

	def minDays(self, n: int) -> int:
		if n <= 1:
			return n
		q = collections.deque()
		q.append([n, 0])
		visited = set([n])
		while len(q) > 0:
			(x, d) = q.popleft()
			if x == 0:
				return d
			neighbors = [x - 1]
			if x % 2 == 0:
				neighbors.append(x // 2)
			if x % 3 == 0:
				neighbors.append(x // 3)
			for y in neighbors:
				if y in visited:
					continue
				q.append([y, d + 1])
				visited.add(y)
		g = {1: 1}
		x = 1
		for i in range(0, 30):
			for j in range(0, 20):
				x = 2 ** i * 3 ** j
				if x <= 1000000000:
					g[x] = i + j
		days = 0
		while n > 1 and n not in g:
			days += 1
			n -= 1
		if n in g:
			days += g[n]
		return days
		f = [None] * (n + 1)
		f[1] = 1
		for k in range(2, n + 1):
			f[k] = 1 + f[k - 1]
			if k % 2 == 0:
				f[k] = min(f[k], 1 + f[k // 2])
			if k % 3 == 0:
				f[k] = min(f[k], 1 + f[k // 3])
		return f[n]


class Solution:

	def minDays(self, n: int) -> int:
		q = deque()
		q.append((n, 0))
		visited = set()
		visited.add(n)
		while q:
			(cur, numSteps) = q.popleft()
			if cur == 0:
				return numSteps
			if cur - 1 not in visited:
				q.append((cur - 1, numSteps + 1))
				visited.add(cur - 1)
			if cur % 2 == 0 and cur // 2 not in visited:
				q.append((cur // 2, numSteps + 1))
				visited.add(cur // 2)
			if cur % 3 == 0 and cur // 3 not in visited:
				q.append((cur // 3, numSteps + 1))
				visited.add(cur // 3)
		return 0


class Solution:

	def minDays(self, n: int) -> int:
		cache = {n: 1}
		q = [n]
		level = 0
		while q:
			_q = []
			for val in q:
				if val == 0:
					return level
				_val = val - 1
				if _val not in cache and _val >= 0:
					cache[_val] = 1
					_q.append(_val)
				_val = val - val // 2
				if _val not in cache and val % 2 == 0 and (_val >= 0):
					cache[_val] = 1
					_q.append(_val)
				_val = val - 2 * val // 3
				if _val not in cache and val % 3 == 0 and (_val >= 0):
					cache[_val] = 1
					_q.append(_val)
			q = _q
			level += 1
		return -1


class Solution:

	def minDays(self, n: int) -> int:

		@lru_cache(None)
		def solve(n):
			if n <= 1:
				return n
			return 1 + min(n % 2 + solve(n // 2), n % 3 + solve(n // 3))
		return solve(n)


import heapq

class Solution:

	def minDays(self, n: int) -> int:
		heap = [[0, n]]
		covered = set()
		while True:
			node = heapq.heappop(heap)
			if node[1] == 0:
				return node[0]
			if node[1] not in covered:
				covered.add(node[1])
				heapq.heappush(heap, [node[0] + 1, node[1] - 1])
			if node[1] % 2 == 0 and node[1] // 2 not in covered:
				covered.add(node[1])
				heapq.heappush(heap, [node[0] + 1, node[1] // 2])
			if node[1] % 3 == 0 and node[1] // 3 not in covered:
				covered.add(node[1])
				heapq.heappush(heap, [node[0] + 1, node[1] // 3])


class Solution:

	def minDays(self, n: int) -> int:
		queue = set([n])
		res = 0
		while queue:
			tmp = set()
			res += 1
			for a in queue:
				if a == 1:
					return res
				if a % 2 == 0 and a // 2 not in queue:
					tmp.add(a // 2)
				if a % 3 == 0 and a // 3 not in queue:
					tmp.add(a // 3)
				tmp.add(a - 1)
			queue = tmp
		return res


class Solution:

	def minDays(self, n: int) -> int:

		def recur(n: int) -> int:
			if n <= 1:
				return n
			if n >= self.N or self.arr[n] == -1:
				ans = 1 + min(n % 2 + recur(n // 2), n % 3 + recur(n // 3))
				if n < self.N:
					self.arr[n] = ans
			else:
				ans = self.arr[n]
			return ans
		self.N = min(100000, n)
		self.arr = [-1] * self.N
		return recur(n)


class Solution:

	def minDays(self, n: int) -> int:
		frontier = deque()
		visited = dict()
		visited[n] = 0
		frontier.append(n)
		while frontier:
			curr = frontier.popleft()
			if curr == 0:
				return visited[curr]
			neighbors = [curr - 1]
			if curr % 2 == 0:
				neighbors.append(curr // 2)
			if curr % 3 == 0:
				neighbors.append(curr // 3)
			for nbr in neighbors:
				if nbr not in visited:
					visited[nbr] = visited[curr] + 1
					frontier.append(nbr)
		return -1


class Solution:

	def minDays(self, n: int) -> int:
		self.ans = float('inf')

		@lru_cache(None)
		def search(days, num):
			if num == 0:
				if days < self.ans:
					self.ans = days
				return
			if days + int(math.log(num) / math.log(3)) + 1 >= self.ans:
				return
			days += 1
			if not num % 3:
				search(days, num // 3)
			if not num % 2:
				search(days, num // 2)
			search(days, num - 1)
			return
		search(0, n)
		return self.ans


class Solution:

	def minDays(self, n: int) -> int:
		if n == 1:
			return 1
		q = collections.deque([(n, 0)])
		visited = set([n])
		while q:
			(c, step) = q.pop()
			step += 1
			if c % 3 == 0:
				nc = c // 3
				if nc == 1:
					return step + 1
				if nc not in visited:
					visited.add(nc)
					q.appendleft((nc, step))
			if c % 2 == 0:
				nc = c // 2
				if nc == 1:
					return step + 1
				if nc not in visited:
					visited.add(nc)
					q.appendleft((nc, step))
			if c - 1 == 1:
				return step + 1
			q.appendleft((c - 1, step))
		return -1


class Solution:

	def minDays(self, n: int) -> int:
		import sys
		from collections import deque
		MAX = sys.maxsize
		mem = {}
		q = deque()
		q.append((n, 0))
		while q:
			(i, op) = q.popleft()
			if i == 0:
				return op
			if i not in mem:
				q.append((i - 1, op + 1))
				if i % 2 == 0:
					q.append((int(i - i / 2), op + 1))
				if i % 3 == 0:
					q.append((int(i - i / 3 * 2), op + 1))
				mem[i] = op


memo = {}
f = min

class Solution:

	def minDays(self, n: int) -> int:
		if n == 0:
			return 0
		if n == 1:
			return 1
		if n in memo:
			return memo[n]
		sol = min(self.minDays(n // 2) + n % 2 + 1, self.minDays(n // 3) + n % 3 + 1)
		memo[n] = sol
		return sol


class Solution:

	def minDays(self, n: int) -> int:
		q = deque([(n, 0)])
		seen = {n}
		while q:
			(curr, cost) = q.popleft()
			if curr == 0:
				return cost
			for nxt in [curr - 1, curr / 3, curr / 2]:
				if nxt != int(nxt):
					continue
				nxt = int(nxt)
				if nxt in seen:
					continue
				seen.add(nxt)
				q.append([nxt, cost + 1])


class Solution:

	def minDays(self, n: int) -> int:
		queue = deque([[n, 0]])
		vis = set()
		while len(queue):
			(curr, days) = queue.popleft()
			if curr in vis:
				continue
			if curr == 0:
				return days
			vis.add(curr)
			if curr % 3 == 0:
				queue.append([curr / 3, days + 1])
			if curr % 2 == 0:
				queue.append([curr / 2, days + 1])
			queue.append([curr - 1, days + 1])


class Solution:

	def minDays(self, n: int) -> int:

		def number_of_steps(i):
			Q = deque()
			seen_before = set()
			steps = 0
			Q.append((i, steps))
			while True:
				(j, steps) = Q.popleft()
				if j == 1:
					return steps
				if j % 3 == 0:
					branch(Q, seen_before, steps, j - 2 * j // 3)
				if j % 2 == 0:
					branch(Q, seen_before, steps, j // 2)
				branch(Q, seen_before, steps, j - 1)

		def branch(Q, seen_before, steps, k):
			if k not in seen_before:
				seen_before.add(k)
				Q.append((k, steps + 1))
		return number_of_steps(n) + 1


import sys

class Solution:

	def minDays(self, n: int) -> int:
		sys.setrecursionlimit(10 ** 6)
		return self.helperFunction(n, {})

	def helperFunction(self, n, d):
		if n <= 0:
			return 0
		if d.get(n) is not None:
			return d[n]
		d[n] = 999999
		if n % 2 == 0:
			d[n] = min(d[n], 1 + self.helperFunction(n - n / 2, d))
		if n % 3 == 0:
			d[n] = min(d[n], 1 + self.helperFunction(n - 2 * n / 3, d))
		if n <= 1024 or n % 2 > 0 or n % 3 > 0:
			d[n] = min(d[n], 1 + self.helperFunction(n - 1, d))
		return d[n]


class Solution:

	def minDays(self, n: int) -> int:
		d = 1
		poss = set([n])
		while 1 not in poss:
			d += 1
			new_poss = set()
			for i in poss:
				new_poss.add(i - 1)
				if i % 2 == 0:
					new_poss.add(i // 2)
				if i % 3 == 0:
					new_poss.add(i // 3)
			poss = new_poss
		return d


class Solution:

	def minDays(self, n: int) -> int:
		buf = {n}
		for i in range(1, n + 1):
			if 1 in buf:
				return i
			(old, buf) = (buf, set())
			for x in old:
				buf.add(x - 1)
				if x % 2 == 0:
					buf.add(x // 2)
				if x % 3 == 0:
					buf.add(x // 3)


class Solution:

	def minDays(self, n: int) -> int:
		if n == 1:
			return 1
		cnt = 0
		st = set([n])
		while st:
			cnt += 1
			st_temp = set()
			for v in st:
				if v == 1:
					return cnt
				st_temp.add(v - 1)
				if v % 2 == 0:
					st_temp.add(v // 2)
				if v % 3 == 0:
					st_temp.add(v // 3)
			st = st_temp


class Solution:

	def minDays(self, n: int) -> int:
		result = 0
		q = [n]
		while q:
			next = set()
			for remain in q:
				if remain == 1:
					return result + 1
				if remain % 2 == 0:
					next.add(remain // 2)
				if remain % 3 == 0:
					next.add(remain // 3)
				next.add(remain - 1)
			result += 1
			q = next
		return result


class Solution:

	def minDays(self, n: int) -> int:
		state = set([n])
		steps = 0
		while 0 not in state:
			nstate = set()
			for x in state:
				nstate.add(x - 1)
				if x % 2 == 0:
					nstate.add(x // 2)
				if x % 3 == 0:
					nstate.add(x // 3)
			steps += 1
			state = nstate
		return steps


class Solution:

	def minDays(self, n: int) -> int:
		day = 0
		options = set([n])
		while 0 not in options:
			new_options = set()
			day += 1
			for o in options:
				new_options.add(o - 1)
				if not o % 2:
					new_options.add(o // 2)
				if not o % 3:
					new_options.add(o // 3)
			options = set(new_options)
		return day


class Solution:

	def minDays(self, n: int) -> int:
		q = [n]
		res = 0
		while q:
			tmp = set()
			for curr in q:
				if curr == 0:
					return res
				tmp.add(curr - 1)
				if curr % 3 == 0:
					tmp.add(curr // 3)
				if curr % 2 == 0:
					tmp.add(curr // 2)
			q = tmp
			res += 1
		return res


class Solution:

	def minDays(self, n: int) -> int:
		queue = [(n, 0)]
		visited = set()
		while queue:
			(remain, day) = queue.pop(0)
			if remain == 0:
				return day
			if remain % 2 == 0 and remain // 2 not in visited:
				queue.append((remain // 2, day + 1))
				visited.add(remain // 2)
			if remain % 3 == 0 and remain // 3 not in visited:
				queue.append((remain // 3, day + 1))
				visited.add(remain // 3)
			if remain - 1 not in visited:
				queue.append((remain - 1, day + 1))


class Solution:

	def minDays(self, n: int) -> int:
		cur = {n}
		res = 0
		while cur:
			temp = set()
			for x in cur:
				if x == 0:
					return res
				temp.add(x - 1)
				if x % 2 == 0:
					temp.add(x // 2)
				if x % 3 == 0:
					temp.add(x // 3)
			res += 1
			cur = temp
		return res


class Solution:

	def minDays(self, n: int) -> int:
		s = {n}
		for i in itertools.count(1):
			if 1 in s:
				return i
			nxt = set()
			for x in s:
				nxt.add(x - 1)
				if x % 2 == 0:
					nxt.add(x >> 1)
				if x % 3 == 0:
					nxt.add(x // 3)
			s = nxt


class Solution:

	def minDays(self, n: int) -> int:
		if n == 0:
			return 0
		q = set([n])
		level = 0
		while q:
			nq = set()
			level += 1
			for item in q:
				if item == 1:
					return level
				nq.add(item - 1)
				if item % 2 == 0:
					nq.add(item // 2)
				if item % 3 == 0:
					nq.add(item // 3)
			q = nq


class Solution:

	def minDays(self, n: int) -> int:
		q = [(0, n)]
		visited = set()
		while q:
			(x, curr) = heapq.heappop(q)
			if curr == 1:
				return x + 1
			if curr not in visited:
				visited.add(curr)
				heapq.heappush(q, (x + 1 + curr % 2, curr // 2))
				heapq.heappush(q, (x + 1 + curr % 3, curr // 3))
		return n


class Solution:

	def minDays(self, n: int) -> int:
		queue = [[0, n]]
		visit = set()
		while queue:
			(curr, num) = heapq.heappop(queue)
			if num == 0:
				return curr
			if num not in visit:
				visit.add(num)
				if num % 3 == 0:
					heapq.heappush(queue, [curr + 1, num // 3])
				if num % 2 == 0:
					heapq.heappush(queue, [curr + 1, num // 2])
				heapq.heappush(queue, [curr + 1, num - 1])


from collections import defaultdict

class Solution:

	def minDays(self, n):
		dic = {n: 0}
		while 0 not in dic:
			temp = defaultdict(int)
			for (i, v) in list(dic.items()):
				if i % 2 == 0:
					temp[i // 2] = v + 1
				if i % 3 == 0:
					temp[i // 3] = v + 1
				temp[i - 1] = v + 1
			dic = temp.copy()
		return dic[0]


class Solution:

	def minDays(self, n: int) -> int:
		step = 0
		cur = {n}
		while 0 not in cur:
			new_cur = set()
			for i in cur:
				new_cur.add(i - 1)
				if not i % 2:
					new_cur.add(i // 2)
				if not i % 3:
					new_cur.add(i // 3)
			cur = new_cur
			step += 1
		return step


class Solution:

	def minDays(self, n: int) -> int:
		step = 0
		tries = set([n])
		while len(tries) > 0:
			nt = set()
			step += 1
			for t in tries:
				if t == 1:
					return step
				if t % 2 == 0:
					nt.add(t // 2)
				if t % 3 == 0:
					nt.add(t // 3)
				nt.add(t - 1)
			tries = nt
		return -1


class Solution:

	def minDays(self, n: int) -> int:
		day_dict = set([n])
		day = 0
		while True:
			day_next = []
			for num in day_dict:
				if num % 2 == 0:
					day_next.append(num // 2)
				if num % 3 == 0:
					day_next.append(num // 3)
				day_next.append(num - 1)
			day += 1
			day_dict = set(day_next)
			if 0 in day_next:
				return day
		return


class Solution:

	def minDays(self, n: int) -> int:
		q = collections.deque()
		days = 0
		q.append(n)
		seen = set()
		seen.add(n)
		while q:
			size = len(q)
			for i in range(size):
				cur = q.popleft()
				if cur == 0:
					return days
				if cur - 1 not in seen:
					seen.add(cur - 1)
					q.append(cur - 1)
				if cur % 2 == 0 and cur % 2 not in seen:
					q.append(cur // 2)
				if cur % 3 == 0 and cur % 3 not in seen:
					q.append(cur // 3)
			days += 1
		return -1