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

Difficulty: interview

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 n == 1 return 1
            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])
        #print(dp)
        
        #for i in range(25,35):
        #    print(i, 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:
        # @lru_cache(None)
        # def helper(n):
            # if n in self.mp:
            #     return self.mp[n]
            if n == 1:
                return 1
            cnt = 0
            st = set()
            st.add(n)
            while st:
                cnt += 1
                # cand = n + 1
                st_temp = set()
                for v in st:
                    # if v in self.mp:
                    #     cand = min(cand, self.mp[v])
                    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)
                # if cand != n + 1:
                #     return cand + cnt
                st = st_temp
            return -1
        # self.mp = self.mp_gen()
        # return helper(n)


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 minDays(self, n: int) -> int:
        queue = collections.deque()
        
        queue.append(n)
        level = 0
        seen = set()
        while queue:
            subList = set()
            for i in range(len(queue)):
                oranges = queue.popleft()
                if oranges not in seen:
                    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 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:
        '''
        # DFS => MLE
        sys.setrecursionlimit(2000000000)
        self.dp = {}
        return self.helper(n)
        '''
        
        '''
        # BFS
        '''
        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)]#(#apples remained,days passed)
        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)))
            # print(poses)

        days=sorted(poses,key=lambda x:x[0])[0][1]

        return days

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 min(
                m % 2 + 1 + dp(m // 2),
                m % 3 + 1 + dp(m // 3)
            )
        return dp(n)

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])
        # dp = [[n] * 3 for _ in range(n+1)]
        
        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
            # print(last)
            if any(n == 0 for n in last):
                return i
            # dp[0] = min(last) - 1
            # dp[1] = min_2(last)
            # dp[2] = min_3(last)
            # print(dp, last)
            # if any(dp[i] == 0 for i in range(3)):
            #     return i
            # for d in dp:
            #     last.add(d)
            # dp = dp[:]
        # print('-' * 20)
        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 minDays(self, n: int) -> int:
        ONE_LIMIT = 100
        TWO_LIMIT = 30
        f = {1:1}
        def search(n, one, two):
            # if n == 1 return 1
            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 __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:
#         # self.hit0 = 0
#         # self.hit1 = 0
#         # self.total = 0
        
#         # cache = {0: 0}
#         # return self._find(n, cache, inf)
        
#         return self._find(n, {0: 0}, inf)
        
#         # self._find(n, cache, inf)
#         # hit = self.hit0 + self.hit1
#         # print(self.total, hit, self.hit0, self.hit1, hit / self.total, self.hit0 / hit)
        
#         # print(cache)
#         # return cache[n]


#     def _find(self, n, cache, terminate):
        
#         if n in cache:
#             return cache[n]
        
#         # # self.total += 1
#         # if n in cache:
#         #     if cache[n] > terminate:
#         #         # self.hit0 += 1
#         #         return inf
#         #     # self.hit1 += 1
#         #     return cache[n]
        
#         if terminate <= 0:
#             return inf
        
#         oldTerminate = terminate
#         ret = inf
#         if n % 3 == 0:
#             ret = 1 + self._find(n // 3, cache, terminate - 1)
#             terminate = min(terminate, ret - 1)
#         if n % 2 == 0:
#             ret = min(ret, 1 + self._find(n // 2, cache, terminate - 1))
#             terminate = min(terminate, ret - 1)
#         ret = min(ret, 1 + self._find(n - 1, cache, terminate - 1))
        
#         # if ret < inf:
#         #     cache[n] = ret
#         # return ret
        
#         if ret <= oldTerminate:
#             cache[n] = ret
#             return ret
#         return inf


# class Solution:
#     def minDays(self, n: int) -> int:
#         return self._find(n, {0: 0}, inf)
    
    
#     def _find(self, n, cache, terminate):

#         if n in cache:
#             return cache[n]
        
#         if terminate <= -15:
#             return inf
        
#         ret = inf
#         if n % 3 == 0:
#             ret = 1 + self._find(n // 3, cache, terminate - 1)
#             terminate = min(terminate, ret - 1)
#         if n % 2 == 0:
#             ret = min(ret, 1 + self._find(n // 2, cache, terminate - 1))
#             terminate = min(terminate, ret - 1)
#         ret = min(ret, 1 + self._find(n - 1, cache, terminate - 1))
        
#         if ret < inf:
#             cache[n] = ret
#         return ret


# class Solution:
#     def minDays(self, n: int) -> int:
#         arr = [0]
#         for i in range(1, n + 1):
#             n = arr[-1]
#             if i % 2 == 0:
#                 n = min(n, arr[i // 2])
#             if i % 3 == 0:
#                 n = min(n, arr[i // 3])
#             arr.append(n + 1)
        
#         return arr[-1]


# class Solution:
#     def minDays(self, n: int) -> int:
#         return self._find(n, {0: 0})
    
    
#     def _find(self, n, cache):

#         if n in cache:
#             return cache[n]
        
#         ret = inf
#         if n % 3 == 0:
#             ret = 1 + self._find(n // 3, cache)
#         if n % 2 == 0:
#             ret = min(ret, 1 + self._find(n // 2, cache))
#         if n < 50000:
#             ret = min(ret, 1 + self._find(n - 1, cache, terminate - 1))
        

#         return ret


# from collections import deque

# class Solution:
#     def minDays(self, n: int) -> int:
#         q1 = deque([0, None])
#         q2 = deque([n, None])
#         visited = {n}
        
#         for i in range(n):
#             tmp = set()
#             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 visited:
#                         return i * 2 + 1
#                     if m not in tmp:
#                         tmp.add(m)
#                         q1.append(m)
#             visited = tmp
            
#             tmp = set()
#             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 visited:
#                         return i * 2 + 2
#                     if m not in tmp:
#                         q2.append(m)
#                         tmp.add(m)
#             visited = tmp


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:
                        q2.append(m)
                        visited2.add(m)


# class Solution:
#     def minDays(self, n: int) -> int:
#         # self.hit0 = 0
#         # self.hit1 = 0
#         # self.total = 0
        
#         # cache = {0: 0}
#         # return self._find(n, cache, inf)
        
#         return self._find(n, {0: 0}, inf)
        
#         # self._find(n, cache, inf)
#         # hit = self.hit0 + self.hit1
#         # print(self.total, hit, self.hit0, self.hit1, hit / self.total, self.hit0 / hit)
        
#         # print(cache)
#         # return cache[n]


#     def _find(self, n, cache, terminate):
        
#         if n in cache:
#             return cache[n]
        
#         # # self.total += 1
#         # if n in cache:
#         #     if cache[n] > terminate:
#         #         # self.hit0 += 1
#         #         return inf
#         #     # self.hit1 += 1
#         #     return cache[n]
        
#         if terminate <= 0:
#             return inf
        
#         oldTerminate = terminate
#         ret = inf
#         if n % 3 == 0:
#             ret = 1 + self._find(n // 3, cache, terminate - 1)
#             terminate = min(terminate, ret - 1)
#         if n % 2 == 0:
#             ret = min(ret, 1 + self._find(n // 2, cache, terminate - 1))
#             terminate = min(terminate, ret - 1)
#         ret = min(ret, 1 + self._find(n - 1, cache, terminate - 1))
        
#         # if ret < inf:
#         #     cache[n] = ret
#         # return ret
        
#         if ret <= oldTerminate:
#             cache[n] = ret
#             return ret
#         return inf


# class Solution:
#     def minDays(self, n: int) -> int:
#         return self._find(n, {0: 0}, inf)
    
    
#     def _find(self, n, cache, terminate):

#         if n in cache:
#             return cache[n]
        
#         if terminate <= -15:
#             return inf
        
#         ret = inf
#         if n % 3 == 0:
#             ret = 1 + self._find(n // 3, cache, terminate - 1)
#             terminate = min(terminate, ret - 1)
#         if n % 2 == 0:
#             ret = min(ret, 1 + self._find(n // 2, cache, terminate - 1))
#             terminate = min(terminate, ret - 1)
#         ret = min(ret, 1 + self._find(n - 1, cache, terminate - 1))
        
#         if ret < inf:
#             cache[n] = ret
#         return ret


# class Solution:
#     def minDays(self, n: int) -> int:
#         arr = [0]
#         for i in range(1, n + 1):
#             n = arr[-1]
#             if i % 2 == 0:
#                 n = min(n, arr[i // 2])
#             if i % 3 == 0:
#                 n = min(n, arr[i // 3])
#             arr.append(n + 1)
        
#         return arr[-1]


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:
        
        self.best = math.inf
        
        @lru_cache(None)
        def f(n, steps):
            if n == 0:
                self.best = min(self.best, steps)
                return steps
            
            if steps > self.best:
                return math.inf
            if n % 3 == 0:
                f(n // 3, steps + 1)
            if n % 2 == 0:
                f(n // 2, 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

from queue import Queue
class Solution:
    def minDays(self, n: int) -> int:
        q=Queue()
        q.put((n,0))
        visited=set()
        while True:
            num,days=q.get()
            if num not in visited:
                visited.add(num)
                if num==0:
                    return days
                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))

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.best = math.inf
        
        @lru_cache(None)
        def f(n, steps):
            if n == 0:
                self.best = min(self.best, steps)
                return steps
            
            if steps > self.best:
                return math.inf
            if n % 3 == 0:
                f(n // 3, steps + 1)
            if steps > self.best:
                return math.inf
            
            if n % 2 == 0:
                f(n // 2, steps + 1)
            if steps > self.best:
                return math.inf

            f(n-1, steps + 1)
        
        f(n, 0)
        return self.best

class Solution:
    # @lru_cache()
    # ^
    # what's this?
    def minDays(self, n: int) -> int:
        # # Method 1: DP -> TLE
        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
        # return dp[-1]
        
        # # Method 3: Gready -> Dijkstra?
        def dfs(n):
            # print(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)
        
        # # Method 2: DP -> TLE
        # dp = [0, 1] + [float('inf')] * (n-1)
        # for i in range(1, n+1):
        #     if i+1 <= n:
        #         dp[i+1] = min(dp[i+1], dp[i] + 1)
        #     if i*2 <= n:
        #         dp[i*2] = min(dp[i*2], dp[i] + 1)
        #     if i*3 <= n:
        #         dp[i*3] = min(dp[i*3], dp[i] + 1)
        # return dp[-1]
        
        # # Method 4: DFS
        # # DFS
        # def dfs(n):
        #     if n == 1:
        #         return 1
        #     else:
        #         print(n)
        #         if n % 3 == 0:
        #             print(\"case 3\")
        #             v3 = dfs(n//3) + 1
        #             self.ans.append(v3)
        #         if n % 2 == 0:
        #             print('case 2')
        #             v2 = dfs(n//2) + 1
        #             self.ans.append(v2)
        #         if n - 1 > 1:
        #             print('case 1')
        #             v1 = dfs(n-1) + 1
        #             self.ans.append(v1)
        # dfs(n)
        # return min(self.ans)


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:
    # @lru_cache()
    # ^
    # what's this?
    def minDays(self, n: int) -> int:
        # # # Method 1: DP -> TLE
        # dp = [0, 1] + [float('inf')] * (n-1)
        # for i in range(2,n+1):
        #     v = []
        #     v.append(i%2 + dp[i//2])
        #     v.append(i%3 + dp[i//3])
        #     dp[i] = min(v) + 1
        # return dp[-1]
        
        # Method 2 -> Dijkstra?
        
        # # Method 3: Gready + DP -> AC
        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):
            # print(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)
        
        # # Method 4: DP -> TLE
        # dp = [0, 1] + [float('inf')] * (n-1)
        # for i in range(1, n+1):
        #     if i+1 <= n:
        #         dp[i+1] = min(dp[i+1], dp[i] + 1)
        #     if i*2 <= n:
        #         dp[i*2] = min(dp[i*2], dp[i] + 1)
        #     if i*3 <= n:
        #         dp[i*3] = min(dp[i*3], dp[i] + 1)
        # return dp[-1]
        
        # # Method 5: DFS
        # # DFS
        # def dfs(n):
        #     if n == 1:
        #         return 1
        #     else:
        #         print(n)
        #         if n % 3 == 0:
        #             print(\"case 3\")
        #             v3 = dfs(n//3) + 1
        #             self.ans.append(v3)
        #         if n % 2 == 0:
        #             print('case 2')
        #             v2 = dfs(n//2) + 1
        #             self.ans.append(v2)
        #         if n - 1 > 1:
        #             print('case 1')
        #             v1 = dfs(n-1) + 1
        #             self.ans.append(v1)
        # dfs(n)
        # return min(self.ans)


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:
    # @lru_cache()
    def minDays(self, n: int) -> int:
        # # Method 1: DP -> TLE
        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
        # return dp[-1]
        
        # # Method 3: Gready -> Dijkstra?
        def dfs(n):
            # print(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)
        
        # # Method 2: DP -> TLE
        # dp = [0, 1] + [float('inf')] * (n-1)
        # for i in range(1, n+1):
        #     if i+1 <= n:
        #         dp[i+1] = min(dp[i+1], dp[i] + 1)
        #     if i*2 <= n:
        #         dp[i*2] = min(dp[i*2], dp[i] + 1)
        #     if i*3 <= n:
        #         dp[i*3] = min(dp[i*3], dp[i] + 1)
        # return dp[-1]
        
        # # Method 4: DFS
        # # DFS
        # def dfs(n):
        #     if n == 1:
        #         return 1
        #     else:
        #         print(n)
        #         if n % 3 == 0:
        #             print(\"case 3\")
        #             v3 = dfs(n//3) + 1
        #             self.ans.append(v3)
        #         if n % 2 == 0:
        #             print('case 2')
        #             v2 = dfs(n//2) + 1
        #             self.ans.append(v2)
        #         if n - 1 > 1:
        #             print('case 1')
        #             v1 = dfs(n-1) + 1
        #             self.ans.append(v1)
        # dfs(n)
        # return min(self.ans)


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

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:
        q = [n]
        v = set()
        steps = 0
        while len(q) > 0:
            newq = []
            while len(q) > 0:
                node = q.pop()
                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:
    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:
        mem = {1:1}
        @lru_cache(None)
        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:
        
        self.best = math.inf
        
        @lru_cache(None)
        def f(n, steps):
            if n == 0:
                self.best = min(self.best, steps)
                return steps
            
            if steps > self.best:
                return math.inf
            ans = math.inf
            if n % 3 == 0:
                ans = min(ans, f(n // 3, steps + 1))
            if n % 2 == 0:
                ans = min(ans, f(n // 2, steps + 1))

            ans = min(ans, f(n-1, steps + 1))
            return ans
        
        return f(n, 0)

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

from queue import Queue
class Solution:
    def minDays(self, n: int) -> int:
        q=Queue()
        q.put((n,0))
        visited=set()
        while True:
            num,days=q.get()
            if num in visited:
                continue
            visited.add(num)
            if num==0:
                return days
            days+=1
            if num%3==0:
                q.put((num//3,days))
            
            if num%2==0:
                q.put((num//2,days))
            q.put((num-1,days))

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)
            # print(q1, seen1, step)
            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()
                # print(left ,days)

                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 1e10
            if n == 0:
                return 0
            
            if n % 3 == 0:
                op3 = dfs(n//3, k+1) + 1
            else:
                op3 = 1e10

            if n % 2 == 0:
                op2 = dfs(n//2, k+1) + 1
            else:
                op2 = 1e10
        
            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:
        return self.dfs(n)
    
    @lru_cache(None)
    def dfs(self, n):
        if n < 2:
            return n
        if n < 0:
            return -1
        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:
        q=[n]
        seen = set()
        res=0
        while q:
            nq=[]
            for x in q: # SIMPLE BFS
                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:
    # @lru_cache()
    def minDays(self, n: int) -> int:
        # # Method 1: DP -> TLE
        self.m = 1000
        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
        # return dp[-1]
        
        # # Method 3: Gready -> Dijkstra?
        def dfs(n):
            # print(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)
        
        # # Method 2: DP -> TLE
        # dp = [0, 1] + [float('inf')] * (n-1)
        # for i in range(1, n+1):
        #     if i+1 <= n:
        #         dp[i+1] = min(dp[i+1], dp[i] + 1)
        #     if i*2 <= n:
        #         dp[i*2] = min(dp[i*2], dp[i] + 1)
        #     if i*3 <= n:
        #         dp[i*3] = min(dp[i*3], dp[i] + 1)
        # return dp[-1]
        
        # # Method 4: DFS
        # # DFS
        # def dfs(n):
        #     if n == 1:
        #         return 1
        #     else:
        #         print(n)
        #         if n % 3 == 0:
        #             print(\"case 3\")
        #             v3 = dfs(n//3) + 1
        #             self.ans.append(v3)
        #         if n % 2 == 0:
        #             print('case 2')
        #             v2 = dfs(n//2) + 1
        #             self.ans.append(v2)
        #         if n - 1 > 1:
        #             print('case 1')
        #             v1 = dfs(n-1) + 1
        #             self.ans.append(v1)
        # dfs(n)
        # return min(self.ans)


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()
            # print(os, days)
            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 = 1e100
            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:
        from functools import lru_cache
        import math
        ans = {}
        @lru_cache(None)
        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 1e10
            if n == 0:
                return 0
            
            if n % 3 == 0:
                op3 = dfs(n//3, k+1) + 1
            else:
                op3 = 1e10

            if n % 2 == 0:
                op2 = dfs(n//2, k+1) + 1
            else:
                op2 = 1e10
        
            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,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
        
        
        
# SEMI OPTIMIZED SOLUTION         
#     def minDays(self, n: int) -> int:
#         if n < 2: return n
#         dp = [math.inf for _ in range(n+1)]
#         dp[0] = 0
#         dp[1] = 1
#         dp[2] = 2
        
#         for i in range(3,n+1):
#             c1,c2,c3 = math.inf,math.inf,math.inf
#             if i%2 == 0:
#                 c1 = dp[i - i//2]+1
#             if i%3 == 0:
#                 c2 = dp[i - 2*(i//3)]+1
#             c3 = dp[i-1]+1
#             dp[i] = min(c1,c2,c3)
            
#         return dp[n]
        
        
        
        
        
        
        
        
        
        
        
        
# ##### BRUTE FORCE        ####
#     def minDays(self, n: int) -> int:
#         self.dic = {}
#         return self.helper(n,0)
    
#     def helper(self, days_left, count):
#         if days_left == 0: return count
#         c1,c2,c3 = math.inf, math.inf, math.inf
#         c1 = self.helper(days_left-1,count+1)
#         if days_left %2 ==0:
#             c2 = self.helper(days_left//2,count+1)
#         if days_left % 3 ==0:
#             c3 = self.helper(days_left//3,count+1)
        
#         return min(c1,c2,c3)



#     def minDays(self, n: int) -> int:
#         if n < 2: return n
#         dp = [math.inf for _ in range(n+1)]
#         dp[0] = 0
#         dp[1] = 1
#         dp[2] = 2
        
#         for i in range(3,n+1):
#             c1,c2,c3 = math.inf,math.inf,math.inf
#             if i%2 == 0:
#                 c1 = dp[i - i//2]+1
#             if i%3 == 0:
#                 c2 = dp[i - 2*(i//3)]+1
#             c3 = dp[i-1]+1
#             dp[i] = min(c1,c2,c3)
            
#         return dp[n]


# from functools import lru_cache

# # 暴力bfs能过，但是是top-down的，比赛的时候我搞错了
# class Solution:
#     def minDays(self, n: int) -> int:
        
#         vis = set()
#         q = collections.deque([n])
#         cost = 1
#         while True:
#             for i in range(len(q)):
#                 cur = q.popleft()
#                 if cur <= 1:
#                     return cost
#                 if cur in vis:
#                     continue
#                 vis.add(cur)
#                 q.append(cur-1)
#                 if not cur % 2:
#                     q.append(cur//2)
#                 if not cur % 3:
#                     q.append(cur//3)
#             cost += 1
                
#         return dfs(n)
    
## 之后是剪枝

## 剪枝一，
class Solution:
    def minDays(self, n: int) -> int:
        ans = 1
        queue = [n]
        seen = set()
        while queue: #bfs 
            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 
            
            
## 剪枝2 https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/discuss/794088/Intuitive-solution-with-Proof

# from functools import lru_cache
# class Solution:
#     def minDays(self, n: int) -> int:
        
#         @lru_cache(None)
#         def helper(n, one=0):
#             if one >= 3:
#                 return math.inf
#             if n < 1: return n
            
#             prev = helper(n - 1, one + 1)
#             if not n % 2:
#                 prev = min(prev, helper(n // 2))
#             if not n % 3:                
#                 prev = min(prev, helper(n // 3))
#             return prev + 1                
        
#         return helper(n)



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

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]
            # t=0
            # if(n%3==0):
            #     b=fun(n-2*n//3,d)+1
            #     t=1
            # elif(n%3==1):
            #     b=fun((n-1)-2*(n-1)//3,d)+2
            #     #b=float(\"inf\")
            #     n=n-1
            #     t=1
            # else:
            #     b=float(\"inf\")
            # #v=fun(n-1,d)+1
            # if(t==0):
            #     if(n%2==0):
            #         a=fun(n//2,d)+1
            #     elif(n%2==1):
            #         a=fun((n-1)-(n-1)//2,d)+2
            #         n=n-1
            # else:
            #     a=float(\"inf\")
            # #if(v1==v2):
            # #      d[v1]=min(a,b)
            # d[n]=min(a,b)
            # 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:
#         memo = {}
#         def helper(n):
#             # base case
#             if n<=1:
#                 return n
#             if n in memo:
#                 return memo[n]
#             minDays = float(\"inf\")
#             # don't need to check helper(n-1)
#             # if n is not divisible by 2, we eat 1 by 1 until it is divisible
#             # if n is not divisible by 3, we eat 1 by 1 until it is divisible
#             minDays = min(n%2 + helper(n//2), n%3 + helper(n//3)) + 1
#             memo[n] = minDays
#             return minDays
        
#         return helper(n)


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):
        # 好题
        # 一共有n个橘子
        # 每天有3中选项吃橘子
        # 要么吃一个
        # 如果橘子数字可以被2整除，吃一半
        # 如果橘子数字可以被3整除，吃1 / 3
        # 问最少几天吃完

        # 思路：经典bfs，queue里放当前剩下的橘子数字即可
        queue = deque([n])
        visited = set()
        steps = 0
        
        # bfs中很经典的一个时间复杂度的优化就是利用visited数组
        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):
        queue = deque([n])
        visited = set()
        visited.add(n)
        
        steps = 0
        
        while queue:
            q_len = len(queue)
            for _ in range(q_len):
                curr = queue.popleft()
                if curr == 0:
                    return steps
                if curr - 1 not in visited:
                    queue.append(curr - 1)
                    visited.add(curr - 1)
                if curr % 2 == 0 and curr // 2 > 0 and curr // 2 not in visited:
                    queue.append(curr // 2)
                    visited.add(curr // 2)
                if curr % 3 == 0 and curr // 3 > 0 and curr // 3 not in visited:
                    queue.append(curr // 3)
                    visited.add(curr // 3)
            steps += 1
        return -1

class Solution:
    def minDays(self, n):
        # 好题
        # 一共有n个橘子
        # 每天有3中选项吃橘子
        # 要么吃一个
        # 如果橘子数字可以被2整除，吃一半
        # 如果橘子数字可以被3整除，吃1 / 3
        # 问最少几天吃完

        # 思路：经典bfs，queue里放当前剩下的橘子数字即可
        queue = deque([n])
        visited = set()
        steps = 1
        
        # bfs中很经典的一个时间复杂度的优化就是利用visited数组
        while queue:
            q_len = len(queue)
            for _ in range(q_len):
                remain = queue.popleft()
                if remain == 0:
                    return steps - 1
                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:
        queue = deque([n])
        visited = set()
        steps = 1
        
        while queue:
            q_len = len(queue)
            for _ in range(q_len):
                remain = queue.popleft()
                if remain == 0:
                    return steps - 1
                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
        
        
#         queue = deque([(n, 1)])
#         steps = 1
        
#         while queue:
#             q_len = len(queue)
#             for _ in range(q_len):
#                 remain, curr = queue.popleft()
#                 remain -= curr
#                 if remain == 0:
#                     print('hehe')
#                     return steps
#                 queue.append((remain, 1))
#                 if remain // 2 > 0 and remain % 2 == 0:
#                     queue.append((remain, remain // 2))
#                 if remain - 2 * remain // 3 > 0 and remain % 3 == 0:
#                     queue.append((remain, remain - 2 * remain // 3))
#             steps += 1
#         return steps


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):
        # DFS
        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:
#         Iterative DFS(Time Limit Exceded)

#         stack = [(n, 0)]
#         minDays = float('inf')
#         seen = {}
#         while stack:
#             numOrgs, curDays = stack.pop()
            
#             if numOrgs == 0:
#                 minDays = min(minDays, curDays)
#                 continue
            
#             if numOrgs < 0:
#                 continue
            
#             stack.append((numOrgs - 1, curDays + 1))
            
#             if numOrgs % 2 == 0:
#                 stack.append((numOrgs - (numOrgs // 2), curDays + 1))
            
#             if numOrgs % 3 == 0:
#                 stack.append((numOrgs - 2 * (numOrgs // 3), curDays + 1))
        
#         return minDays



#         DFS with cache(reached max depth)

#         def dfs(numOrngs):
#             if numOrngs in seen:
#                 return seen[numOrngs]
            
#             if numOrngs == 0:
#                 return 1
            
#             if numOrngs < 0:
#                 return float('inf')
            
#             a = dfs(numOrngs - 1)
            
#             b = float('inf')
#             if numOrngs % 2 == 0:
#                 b = dfs(numOrngs - (numOrngs // 2))
            
#             c = float('inf')
#             if numOrngs % 3 == 0:
#                 c = dfs(numOrngs - 2 * (numOrngs // 3))
            
#             seen[numOrngs] = min(a, b, c) + 1
            
#             return seen[numOrngs]
        
#         seen = {}
#         return dfs(n) - 1
        
        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:
        # 我当时看到数据范围n觉得直接dp(n)会超时因此我就没做。
        # 但是实际上每次都是整除2整除3其实只需要log(n)时间就搞定！
        @lru_cache(None)
        def go(x):
            if x == 0:
                return 0
            
            best = 1e100
            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)
        '''
        @lru_cache(None)
        def dp(x):
            if x <= 1: return x
            res = x
            res = min(res, dp(x//3) + x % 3 + 1)
            res = min(res, dp(x//2) + x % 2 + 1)
            return res
        return dp(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:
        
        days = 0
        fringe = deque([n])
        seen = set()
        
        while fringe:
            for _ in range(len(fringe)):
                n = fringe.popleft()
                if n == 0:
                    return days
                
                if n - 1 not in seen:
                    fringe.append(n - 1)
                    seen.add(n - 1)
                if n % 2 == 0 and n // 2 not in seen:
                    fringe.append(n // 2)
                    seen.add(n // 2)
                if n % 3 == 0 and n // 3 not in seen:
                    fringe.append(n // 3)
                    seen.add(n // 3)
        
            days += 1
        


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]
            
        
        
        
        
        
        
        
        
        
            


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:
        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] # make queue
        dist = {N:0} # distance dictionary. can use this as visited dictionary too!
        #parent = {N:None}
        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
                    #parent[edge] = v
                    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

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

        q = collections.deque([])
        q.append((n, 0))
        seen = set()
        while q:
            oranges, days = q.popleft()
            if oranges <= 3:
                return days + min(2, oranges)
            if oranges % 2 == 0:
                if oranges/2 not in seen:
                    q.append((oranges/2, days+1))
                    seen.add(oranges/2)
            if oranges % 3 == 0:
                if oranges-(2*(oranges/3)) not in seen:
                    q.append((oranges-(2*(oranges/3)), days+1))
                    seen.add(oranges-(2*(oranges/3)))

            if oranges-1 not in seen:
                q.append((oranges-1, days+1))
                seen.add(oranges-1)


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:
            # print(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]] # BFS
        
        covered = set()
        
        while True:
            
            # print(heap, \" ||| \", covered)
            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:
        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 sorted(edges)
    
        q = [N] # make queue
        dist = {N:0} # distance dictionary. can use this as visited dictionary too!
        #parent = {N:None}
        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
                    #parent[edge] = v
                    q.append(edge)
        return dist[0]


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:

        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 not in seen:
                    q.append((os/2, days+1))
                    seen.add(os/2)
            if os % 3 == 0:
                if os-(2*(os/3)) not in seen:
                    q.append((os-(2*(os/3)), days+1))
                    seen.add(os-(2*(os/3)))

            if os-1 not in seen:
                q.append((os-1, days+1))
                seen.add(os-1)
                    
        return days + 1 if not q else days


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)) # n remain, op
        
        while q:
            i, op = q.popleft()
            if i == 0:
                return op
            if i not in mem:
                # get 1
                q.append((i-1, op+1))
                # get m1 when /2
                if i % 2 == 0:
                    q.append((int(i-(i/2)), op+1))
                # get m2 when /3
                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])
        level = 0
        visited = set()
        while q:
            # print(q)
            size = len(q)
            for i in range(size):
                cur = q.popleft()
                if cur == 0:
                    return level
                if cur % 2 == 0 and cur-cur//2 not in  visited:
                    visited.add(cur-cur//2)
                    q.append(cur-cur//2)
                if cur % 3 == 0 and cur-2*cur//3 not in visited:
                    visited.add(cur-2*cur//3)
                    q.append(cur-2*cur//3)
                if cur-1 not in visited:
                    visited.add(cur-1)
                    q.append(cur-1)
            level += 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)

from collections import deque
class Solution:
    def minDays(self, n: int) -> int:
        day=0
        q=deque([n])
        visited=set()
        while q:
            day+=1
            for _ in range(len(q)):
                v =q.popleft()
                if v==1:
                    return day
                if v%3==0 and v%3 not in visited:
                    q.append(v//3)
                    visited.add(v//3)
                if v%2==0:
                    q.append(v//2)
                    visited.add(v//3)
                if v-1 not in visited:
                    q.append(v-1)
                    visited.add(v-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:
                    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 % 3 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)

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)):
                cur = q.popleft()
                if cur == 1:
                    return days
                if cur%2 == 0 and cur%2 not in visited:
                    q.append(cur//2)
                    visited.add(cur//2)
                if cur%3 == 0 and cur%3 not in visited:
                    q.append(cur//3)
                    visited.add(cur//3)
                if cur-1 not in visited:
                    q.append(cur-1)
                    visited.add(cur-1)


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:
        # ret=0
        # while n>=3:
        #     if n%3:
        #         n-=1
        #         ret+=1
        #     else:
        #         n//=3
        #         ret+=1
        # if n==2:
        #     return ret+2
        # if n==1:
        #     return ret+1
        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:
        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:
#         dp = [0] * (n+1)
#         # dp[0] = 1
        
#         for i in range(1, n + 1):
#             # print(i, dp[i-1], i - i/2, i - (2*i/3), i%2, i%3)
#             dp[i] = 1 + min(dp[i-1], 1e9 if i % 2 != 0 else dp[i - int(i/2)], 1e9 if (i % 3 != 0 or i < 2*i/3) else dp[i - int(2*i/3)])
            
#         # print(dp)
            
#         return dp[n]
        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:
        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
            # print(len(st_temp))
        return -1


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 = 1e100
            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:
        result = 0
        q = [n]
        while q:
            #next = []
            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))
            
            
        # dp = {}
        # dp[0] = 0
        # dp[1] = 1
        # for i in range(2, n+1):
        #     if i % 2 == 0 and i % 3 == 0:
        #         dp[i] = min(dp[i//2], dp[i//3], dp[i-1]) + 1
        #     elif i % 2 == 0:
        #         dp[i] = min(dp[i//2], dp[i-1]) + 1
        #     elif i % 3 == 0:
        #         dp[i] = min(dp[i//3], dp[i-1]) + 1
        #     else:
        #         dp[i] = dp[i-1] + 1
        # return dp[n]


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]


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()
                #print(node,q,visited,days)
                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:
        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

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)]#(#apples remained,days passed)
        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)]
                new_poses+=new_pos
            min_apples=min([pos[0] for pos in new_poses])
            poses=set(new_poses)

        days=sorted(poses,key=lambda x:x[0])[0][1]

        return days

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