Given a number N, the task is to count minimum steps to minimize it to 1 according to the following criteria:
	If N is divisible by 2 then you may reduce N to N/2.
	If N is divisible by 3 then you may reduce N to N/3.
	Otherwise, Decrement N by 1.
Example 1:
Input: N = 10
Output: 3
Explanation: 10 - 1 = 9 / 3 = 3 / 3 = 1
Example 2:
Input: N = 1
Output: 0
Explanation: N is 1
Your Task:  
You don't need to read input or print anything. Complete the function minSteps() which takes N as input parameters and returns the integer value
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:

	def minSteps(self, N):

		# code here

Solutions:
class Solution:

	def minSteps(self, N):
		MAX = 100000
		dp = [-1 for i in range(N + 1)]
		dp[1] = 0
		for i in range(2, N + 1):
			dp[i] = 1 + min(dp[i - 1], dp[i // 2] if i % 2 == 0 else MAX, dp[i // 3] if i % 3 == 0 else MAX)
		return dp[N]


class Solution:

	def minSteps(self, N):

		def fun(n, d):
			if n == 1:
				return 0
			if d[n] != -1:
				return d[n]
			res = fun(n - 1, d)
			if n % 2 == 0:
				res = min(res, fun(n // 2, d))
			if n % 3 == 0:
				res = min(res, fun(n // 3, d))
			d[n] = 1 + res
			return d[n]
		d = [-1 for i in range(N + 1)]
		return fun(N, d)


class Solution:

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


class Solution:

	def minSteps(self, n):
		dp = [0] * (N + 1)
		for i in range(2, N + 1):
			dp[i] = dp[i - 1] + 1
			for j in range(2, 4):
				if i % j == 0:
					dp[i] = min(dp[i], dp[i // j] + 1)
		return dp[N]


class Solution:

	def minSteps(self, N):
		dp = [0] * (N + 1)
		for i in range(2, N + 1):
			dp[i] = 1 + min(dp[i // 2] if i % 2 == 0 else float('inf'), dp[i // 3] if i % 3 == 0 else float('inf'), dp[i - 1])
		return dp[N]


class Solution:

	def minSteps(self, N):
		table = [0] * (N + 1)
		table[0] = 0
		table[1] = 0
		for pos in range(2, len(table)):
			a = b = c = float('inf')
			if pos % 3 == 0:
				a = 1 + table[pos // 3]
			if pos % 2 == 0:
				b = 1 + table[pos // 2]
			c = 1 + table[pos - 1]
			table[pos] = min(a, b, c)
		return table[N]


class Solution:

	def minSteps(self, N):
		dp = {}
		dp[0] = -1
		dp[1] = 0
		for i in range(2, N + 1):
			x1 = dp[i - 1] + 1
			x2 = dp[i / 2] + 1 if i % 2 == 0 else N
			x3 = dp[i / 3] + 1 if i % 3 == 0 else N
			dp[i] = min(x1, x2, x3)
		return dp[N]


class Solution:

	def minSteps(self, N):
		d = {1: 0, 2: 1, 3: 1}
		for i in range(4, N + 1):
			arr = [d[i - 1]]
			if i % 2 == 0:
				arr.append(d[i // 2])
			if i % 3 == 0:
				arr.append(d[i // 3])
			d[i] = min(arr) + 1
		return d[N]


class Solution:

	def minSteps(self, N):
		if N == 1:
			return 0
		temp = [-1] * (N + 1)
		temp[1] = 0
		for curr in range(2, N + 1):
			res = temp[curr - 1]
			if curr % 2 == 0:
				res = min(res, temp[curr // 2])
			if curr % 3 == 0:
				res = min(res, temp[curr // 3])
			temp[curr] = 1 + res
		return temp[N]


class Solution:

	def minSteps(self, N):
		memo = {}

		def minSteps1(n):
			if n == 1:
				return 0
			if n in memo:
				return memo[n]
			step1 = float('inf')
			step2 = float('inf')
			if n % 2 == 0:
				step1 = 1 + minSteps1(int(n / 2))
			if n % 3 == 0:
				step2 = 1 + minSteps1(int(n / 3))
			step3 = 1 + minSteps1(n - 1)
			memo[n] = min(step1, step2, step3)
			return memo[n]
		return minSteps1(N)


import sys

class Solution:

	def helper(self, n, dp):
		if n == 1:
			return 0
		if dp[n - 1] == -1:
			ans1 = self.helper(n - 1, dp)
			dp[n - 1] = ans1
		else:
			ans1 = dp[n - 1]
		(ans2, ans3) = (sys.maxsize, sys.maxsize)
		if n % 2 == 0:
			if dp[n // 2] == -1:
				ans2 = self.helper(n // 2, dp)
				dp[n // 2] = ans2
			else:
				ans2 = dp[n // 2]
		if n % 3 == 0:
			if dp[n // 3] == -1:
				ans3 = self.helper(n // 3, dp)
				dp[n // 3] = ans3
			else:
				ans3 = dp[n // 3]
		return 1 + min(ans1, ans2, ans3)

	def minSteps(self, N):
		dp = [-1 for i in range(N + 1)]
		return self.helper(N, dp)


class Solution:

	def minSteps(self, N):

		def fun(n):
			if n == 1:
				return 0
			if dp[n] != -1:
				return dp[n]
			res = 0
			res = fun(n - 1)
			if n % 2 == 0:
				res = min(res, fun(n // 2))
			if n % 3 == 0:
				res = min(res, fun(n // 3))
			dp[n] = 1 + res
			return dp[n]
		dp = [-1] * (N + 1)
		return fun(N)


class Solution:

	def f(self, num, dp):
		if num in dp:
			return dp[num]
		if num == 1:
			dp[num] = 0
			return 0
		(by2, by3) = (1000000, 1000000)
		if num % 2 == 0:
			by2 = 1 + self.f(num / 2, dp)
		if num % 3 == 0:
			by3 = 1 + self.f(num / 3, dp)
		dp[num] = min(1 + self.f(num - 1, dp), by2, by3)
		return dp[num]

	def minSteps(self, N):
		dp = {}
		return self.f(N, dp)


from sys import maxsize as MAX_VALUE

class Solution:

	def minSteps(self, n):
		if N == 1:
			return 0
		if N == 2:
			return 1
		if N == 3:
			return 1
		dp = [-1 for i in range(N + 1)]
		dp[1] = 0
		dp[2] = 1
		dp[3] = 1
		for i in range(4, N + 1):
			ans1 = dp[i - 1]
			(ans2, ans3) = (float('inf'), float('inf'))
			if i % 2 == 0:
				ans2 = dp[i // 2]
			if i % 3 == 0:
				ans3 = dp[i // 3]
			dp[i] = 1 + min(ans1, ans2, ans3)
		return dp[N]


class Solution:

	def minSteps(self, N):
		if N == 1:
			return 0
		if N <= 3:
			return 1
		dp = [0] * (N + 1)
		dp[2] = 1
		dp[3] = 1
		for i in range(4, N + 1):
			a = 987654321
			b = 987654321
			if i % 3 == 0:
				a = dp[i // 3] + 1
			if i % 2 == 0:
				b = dp[i // 2] + 1
			c = dp[i - 1] + 1
			dp[i] = min(a, b, c)
		return dp[-1]


class Solution:

	def minSteps(self, N):
		dp = [-1] * (N + 1)

		def check(N):
			if N == 1:
				return 0
			if dp[N] != -1:
				return dp[N]
			elif N % 2 == 0 and N % 3 == 0:
				dp[N] = 1 + min(min(check(N - 1), check(N // 2)), check(N // 3))
				return dp[N]
			elif N % 2 == 0:
				dp[N] = 1 + min(check(N - 1), check(N // 2))
				return dp[N]
			elif N % 3 == 0:
				dp[N] = 1 + min(check(N - 1), check(N // 3))
				return dp[N]
			else:
				dp[N] = 1 + check(N - 1)
				return dp[N]
		res = check(N)
		return res


def solve(n, dp):
	if n == 1:
		return 0
	ans1 = float('inf')
	if n % 3 == 0:
		if dp[n // 3] == -1:
			ans1 = solve(n // 3, dp)
			dp[n // 3] = ans1
		else:
			ans1 = dp[n // 3]
	ans2 = float('inf')
	if n % 2 == 0:
		if dp[n // 2] == -1:
			ans2 = solve(n // 2, dp)
			dp[n // 2] = ans2
		else:
			ans2 = dp[n // 2]
	if dp[n - 1] == -1:
		ans3 = solve(n - 1, dp)
		dp[n - 1] = ans3
	else:
		ans3 = dp[n - 1]
	ans = 1 + min(ans1, ans2, ans3)
	return ans

class Solution:

	def minSteps(self, N):
		dp = [-1 for i in range(N + 1)]
		ans = solve(N, dp)
		return ans


class Solution:

	def minSteps(self, n):
		import sys
		max_int = sys.maxsize
		dp = [0 for i in range(n + 1)]
		dp
		for i in range(2, n + 1):
			(op1, op2, op3) = (max_int, max_int, max_int)
			if i % 3 == 0:
				op1 = dp[i // 3]
			if i % 2 == 0:
				op2 = dp[i // 2]
			op3 = dp[i - 1]
			dp[i] = min(op1, op2, op3) + 1
		return dp[n]


class Solution:

	def minSteps(self, n):
		if n == 1:
			return 0
		if n == 2:
			return 1
		if n == 3:
			return 1
		dp = [-1 for i in range(n + 1)]
		dp[1] = 0
		dp[2] = 1
		dp[3] = 1
		for i in range(4, n + 1):
			ans1 = dp[i - 1]
			(ans2, ans3) = (float('inf'), float('inf'))
			if i % 2 == 0:
				ans2 = dp[i // 2]
			if i % 3 == 0:
				ans3 = dp[i // 3]
			dp[i] = 1 + min(ans1, ans2, ans3)
		return dp[n]


class Solution:

	def minSteps(self, n):
		if n == 1:
			ans = 0
			return ans
		dp = [-1 for i in range(n + 1)]
		return self.minSteps_to_1(n, dp)

	def minSteps_to_1(self, n, dp):
		if n == 1:
			return 0
		ans1 = sys.maxsize
		if n % 3 == 0:
			if dp[n // 3] == -1:
				ans1 = self.minSteps_to_1(n // 3, dp)
				dp[n // 3] = ans1
			else:
				ans1 = dp[n // 3]
		ans2 = sys.maxsize
		if n % 2 == 0:
			if dp[n // 2] == -1:
				ans2 = self.minSteps_to_1(n // 2, dp)
				dp[n // 2] = ans2
			else:
				ans2 = dp[n // 2]
		if dp[n - 1] == -1:
			ans3 = self.minSteps_to_1(n - 1, dp)
			dp[n - 1] = ans3
		else:
			ans3 = dp[n - 1]
		ans = 1 + min(ans1, ans2, ans3)
		return ans


class Solution:

	def minSteps(self, N):
		if N <= 1:
			return 0
		memo = [999999] * (N + 1)
		memo[0] = 0
		memo[1] = 0
		for i in range(1, N):
			memo[i + 1] = min(memo[i] + 1, memo[i + 1])
			if i * 2 <= N:
				memo[i * 2] = min(memo[i] + 1, memo[i * 2])
			if i * 3 <= N:
				memo[i * 3] = min(memo[i] + 1, memo[i * 3])
		return memo[N]


class Solution:

	def minSteps(self, N):
		memo = [None] * (N + 1)

		def helper(N, memo):
			if N <= 1:
				return 0
			if memo[N]:
				return memo[N]
			op1 = op2 = op3 = 9999999
			op1 = 1 + helper(N - 1, memo)
			if N % 2 == 0:
				op2 = 1 + helper(int(N / 2), memo)
			if N % 3 == 0:
				op3 = 1 + helper(int(N / 3), memo)
			memo[N] = min(op1, op2, op3)
			return memo[N]
		return helper(N, memo)


class Solution:

	def minSteps(self, n):
		dp = {}

		def ways(n):
			if n == 1:
				return 0
			if n in dp:
				return dp[n]
			a = 999999999
			b = 999999999
			c = 999999999
			if n % 2 == 0:
				a = ways(n // 2) + 1
			if n % 3 == 0:
				b = ways(n // 3) + 1
			c = ways(n - 1) + 1
			dp[n] = min(a, b, c)
			return dp[n]
		return ways(n)


class Solution:

	def __init__(self):
		self.dp = [-1 for i in range(0, 10001)]
		self.dp[1] = 1

	def minSteps(self, N):
		if N == 1:
			return 0
		if self.dp[N] != -1:
			return self.dp[N]
		ans1 = 999
		ans2 = 999
		ans3 = 999
		ans1 = self.minSteps(N - 1)
		if N % 2 == 0:
			ans2 = self.minSteps(N // 2)
		if N % 3 == 0:
			ans3 = self.minSteps(N // 3)
		self.dp[N] = 1 + min(ans1, ans2, ans3)
		return self.dp[N]


class Solution:

	def minSteps(self, N):
		dp = [0 for i in range(N + 1)]
		for j in range(2, N + 1):
			ans1 = dp[j - 1]
			ans2 = 9999
			ans3 = 99999
			if j % 2 == 0:
				ans2 = dp[j // 2]
			if j % 3 == 0:
				ans3 = dp[j // 3]
			dp[j] = 1 + min(ans1, ans2, ans3)
		return dp[N]


class Solution:

	def minSteps(self, n):
		dp = [-1 for i in range(n + 1)]
		return self.helper(n, dp)

	def helper(self, n, dp):
		if n == 1:
			return 0
		ans1 = 9999
		if n % 3 == 0:
			if dp[n // 3] == -1:
				ans1 = self.helper(n // 3, dp)
				dp[n // 3] == ans1
			else:
				ans1 = dp[n // 3]
		ans2 = 999
		if n % 2 == 0:
			if dp[n // 2] == -1:
				ans2 = self.helper(n // 2, dp)
				dp[n // 2] = ans2
			else:
				ans2 = dp[n // 2]
		if dp[n - 1] == -1:
			ans3 = self.helper(n - 1, dp)
			dp[n - 1] = ans3
		else:
			ans3 = dp[n - 1]
		ans = 1 + min(ans1, ans2, ans3)
		return ans


class Solution:

	def minSteps(self, N):
		dp = [0] * (N + 1)
		for i in range(2, N + 1):
			res = dp[i - 1]
			if i % 2 == 0:
				res = min(res, dp[i // 2])
			if i % 3 == 0:
				res = min(res, dp[i // 3])
			dp[i] = 1 + res
		return dp[-1]
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.minSteps(N)
		print(ans)


class Solution:

	def reduceto1(self, n, dp):
		if n == 1:
			return 0
		elif n == 2 or n == 3:
			dp[n] = 1
			return 1
		if dp[n - 1] == -1:
			ans1 = self.reduceto1(n - 1, dp)
			ans2 = 10000000
			if n % 2 == 0:
				if dp[n // 2] == -1:
					ans2 = self.reduceto1(int(n / 2), dp)
				else:
					ans2 = dp[n // 2]
			ans3 = 10000000
			if n % 3 == 0:
				if dp[n // 3] == -1:
					ans3 = self.reduceto1(int(n / 3), dp)
				else:
					ans3 = dp[n // 3]
			small = min(ans1, ans2, ans3)
			dp[n] = small + 1
		else:
			small = dp[n - 1]
		return 1 + small

	def minSteps(self, N):
		n = N
		dp = [-1 for i in range(n + 1)]
		return self.reduceto1(n, dp)
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.minSteps(N)
		print(ans)


class Solution:

	def fun(self, n, dp):
		if n == 1:
			return 0
		if dp[n] != 0:
			return dp[n]
		a = float('inf')
		b = float('inf')
		c = float('inf')
		if n % 3 == 0:
			a = 1 + self.fun(n // 3, dp)
		if n % 2 == 0:
			b = 1 + self.fun(n // 2, dp)
		c = 1 + self.fun(n - 1, dp)
		dp[n] = min(a, b, c)
		return dp[n]

	def minSteps(self, N):
		dp = [0] * (N + 1)
		return self.fun(N, dp)
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.minSteps(N)
		print(ans)


import sys

class Solution:

	def minSteps(self, n):
		dp = [-1 for i in range(n + 1)]
		return self.minStepshelper(n, dp)

	def minStepshelper(self, n, dp):
		if n == 1:
			return 0
		op1 = sys.maxsize
		if n % 3 == 0:
			if dp[n // 3] == -1:
				op1 = self.minStepshelper(n // 3, dp)
				dp[n // 3] = op1
			else:
				op1 = dp[n // 3]
		op2 = sys.maxsize
		if n % 2 == 0:
			if dp[n // 2] == -1:
				op2 = self.minStepshelper(n // 2, dp)
				dp[n // 2] = op2
			else:
				op2 = dp[n // 2]
		if dp[n - 1] == -1:
			op3 = self.minStepshelper(n - 1, dp)
			dp[n - 1] = op3
		else:
			op3 = dp[n - 1]
		result = 1 + min(op1, op2, op3)
		return result
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.minSteps(N)
		print(ans)


import sys

class Solution:
	store = {}

	def minSteps(self, N):
		if N <= 1:
			return 0
		if self.store.get(N):
			return self.store[N]
		step1 = step2 = step3 = float('inf')
		if N % 3 == 0:
			step1 = self.minSteps(N / 3)
		if N % 2 == 0:
			step2 = self.minSteps(N / 2)
		step3 = self.minSteps(N - 1)
		ans = min(step1, step2, step3) + 1
		self.store[N] = ans
		return ans
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.minSteps(N)
		print(ans)


class Solution:

	def minSteps(self, n):

		def getMinSteps(n, memo):
			if n == 1:
				return 0
			if memo[n] != -1:
				return memo[n]
			res = getMinSteps(n - 1, memo)
			if n % 2 == 0:
				res = min(res, getMinSteps(n // 2, memo))
			if n % 3 == 0:
				res = min(res, getMinSteps(n // 3, memo))
			memo[n] = 1 + res
			return memo[n]
		memo = [0 for i in range(n + 1)]
		for i in range(n + 1):
			memo[i] = -1
		return getMinSteps(n, memo)


class Solution:

	def minSteps(self, N):
		if N == 1:
			return 0
		if N == 2:
			return 1
		if N == 3:
			return 1
		arr = [0] * (N + 1)
		arr[0] = 0
		arr[1] = 0
		arr[2] = 1
		arr[3] = 1
		for j in range(3, N + 1):
			p = 100000
			q = 100000
			r = arr[j - 1]
			if j % 3 == 0:
				p = arr[j // 3]
			if j % 2 == 0:
				q = arr[j // 2]
			arr[j] = min(p, min(q, r)) + 1
		return arr[N]


import sys

class Solution:

	def minSteps(self, N):
		storage = [-1 for i in range(N + 1)]
		storage[1] = 0
		for i in range(2, N + 1):
			if i % 3 == 0:
				storage[i] = storage[i // 3] + 1
			elif i % 2 == 0:
				ans1 = storage[i // 2]
				ans2 = storage[i - 1]
				storage[i] = min(ans1, ans2) + 1
			else:
				storage[i] = storage[i - 1] + 1
		return storage[N]


class Solution:

	def minSteps(self, N):

		def minsteps(N):
			if N == 1:
				return 0
			if N % 3 == 0:
				if storage[N // 3] != -1:
					steps = storage[N // 3]
				else:
					steps = minsteps(N // 3)
				return steps + 1
			elif N % 2 == 0:
				if storage[N // 2] != -1:
					steps1 = storage[N // 2]
				else:
					steps1 = minsteps(N // 2)
				if storage[N - 1] != -1:
					steps2 = storage[N - 1]
				else:
					steps2 = minsteps(N - 1)
				return min(steps1, steps2) + 1
			else:
				if storage[N - 1] != -1:
					steps = storage[N - 1]
				else:
					steps = minsteps(N - 1)
				return steps + 1
		storage = [-1 for i in range(N)]
		return minsteps(N)


class Solution:

	def minSteps(self, N):
		if N == 1:
			return 0
		if N % 3 == 0:
			steps = self.minSteps(N // 3)
			return steps + 1
		elif N % 2 == 0:
			steps1 = self.minSteps(N // 2)
			steps2 = self.minSteps(N - 1)
			return min(steps1, steps2) + 1
		else:
			steps = self.minSteps(N - 1)
			return steps + 1


class Solution:

	def minSteps(self, N):
		count = 0
		if N == 1:
			return 0

		def get_count(N, count, dp):
			if N == 1:
				return dp[N]
			if dp[N] != 0:
				return dp[N]
			if N % 2 == 0 and N % 3 == 0:
				dp[N] = 1 + min(min(get_count(N // 2, count, dp), get_count(N // 3, count, dp)), get_count(N - 1, count, dp))
			elif N % 2 == 0:
				dp[N] = 1 + min(get_count(N // 2, count, dp), get_count(N - 1, count, dp))
			elif N % 3 == 0:
				dp[N] = 1 + min(get_count(N // 3, count, dp), get_count(N - 1, count, dp))
			else:
				dp[N] = 1 + get_count(N - 1, count, dp)
			return dp[N]
		dp = [0] * (N + 1)
		return get_count(N, count, dp)


class Solution:

	def minSteps(self, N):
		if N == 1:
			return 0
		if N == 2 or N == 3:
			return 1
		dp = [0 for i in range(N + 1)]
		dp[2] = 1
		dp[3] = 1
		for i in range(4, N + 1):
			m = float('inf')
			if i % 2 == 0:
				m = min(m, dp[i // 2] + 1)
			if i % 3 == 0:
				m = min(m, dp[i // 3] + 1)
			m = min(m, dp[i - 1] + 1)
			dp[i] = m
		return dp[N]


class Solution:

	def minSteps(self, N):
		data = [0 for i in range(N + 1)]
		if N < 2:
			return 0
		for i in range(1, N + 1):
			if i % 3 == 0 and i % 2 == 0:
				data[i] = min(data[int(i / 3)], data[int(i / 2)], data[i - 1]) + 1
			elif i % 3 == 0:
				data[i] = min(int(i / 3), min(data[int(i / 3)], data[i - 1]) + 1)
			elif i % 2 == 0:
				data[i] = min(int(i / 2), min(data[int(i / 2)], data[i - 1]) + 1)
			else:
				data[i] = data[i - 1] + 1
		return data[N]


from sys import maxsize as MAX_VALUE

class Solution:

	def minSteps(self, n):
		arr = [69 for i in range(n + 1)]
		arr[1] = 0
		i = 2
		while i <= n:
			ans1 = arr[i - 1]
			ans2 = MAX_VALUE
			ans3 = MAX_VALUE
			if i % 2 == 0:
				ans2 = arr[i // 2]
			if i % 3 == 0:
				ans3 = arr[i // 3]
			arr[i] = 1 + min(ans1, ans2, ans3)
			i += 1
		return arr[n]


from math import inf

class Solution:

	def minSteps(self, n):
		if n < 1:
			return -1
		hm = dict()
		hm[0] = -1
		hm[1] = 0
		for i in range(2, n + 1):
			op1 = op2 = op3 = inf
			if i % 2 == 0:
				op1 = hm[i // 2] + 1
			if i % 3 == 0:
				op2 = hm[i // 3] + 1
			op3 = hm[i - 1] + 1
			hm[i] = min(op1, op2, op3)
		return hm[n]


class Solution:

	def minSteps(self, N):
		dp = [2 ** 63] * (N + 1)
		(dp[0], dp[1]) = (0, 0)
		for i in range(2, N + 1):
			if i % 3 == 0 and i % 2 == 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 recur(self, n):
		import sys
		global dp
		if n == 1:
			return 0
		if n < 0:
			return sys.maxsize
		if dp[n]:
			return dp[n]
		t = sys.maxsize
		th = sys.maxsize
		if n % 2 == 0:
			t = 1 + self.recur(n // 2)
		if n % 3 == 0:
			th = 1 + self.recur(n // 3)
		dp[n] = min(min(t, th), 1 + self.recur(n - 1))
		return dp[n]

	def minSteps(self, N):
		import sys
		dp = [0] * (N + 1)
		for i in range(2, N + 1):
			two = sys.maxsize
			if i % 2 == 0:
				two = 1 + dp[i // 2]
			three = sys.maxsize
			if i % 3 == 0:
				three = 1 + dp[i // 3]
			dp[i] = min(1 + dp[i - 1], min(two, three))
		return dp[-1]


class Solution:

	def recur(self, n):
		import sys
		global dp
		if n == 1:
			return 0
		if n < 0:
			return sys.maxsize
		if dp[n]:
			return dp[n]
		t = sys.maxsize
		th = sys.maxsize
		if n % 2 == 0:
			t = 1 + self.recur(n // 2)
		if n % 3 == 0:
			th = 1 + self.recur(n // 3)
		dp[n] = min(min(t, th), 1 + self.recur(n - 1))
		return dp[n]

	def minSteps(self, N):
		global dp
		dp = [0] * (N + 1)
		return self.recur(N)


class Solution:

	def minSteps(self, N):
		memo = {}

		def helper(n):
			if n in memo:
				return memo[n]
			if n == 1:
				return 0
			a = 1 + helper(n - 1)
			c = float('inf')
			b = float('inf')
			if n >= 2 and n % 2 == 0:
				c = 1 + helper(n / 2)
			if n >= 3 and n % 3 == 0:
				b = 1 + helper(n / 3)
			memo[n] = min(a, b, c)
			return memo[n]
		return helper(N)


class Solution:

	def minSteps(self, N):
		l = [0] * (N + 1)
		for i in range(2, N + 1):
			if i == 2 or i == 3:
				l[i] = 1
				continue
			s1 = s2 = s3 = float('inf')
			if i % 3 == 0:
				s1 = l[i // 3] + 1
			if i % 2 == 0:
				s2 = l[i // 2] + 1
			s3 = l[i - 1] + 1
			l[i] = min(s1, s2, s3)
		return l[-1]


class Solution:
	memo = [-1] * int(100000.0)

	def minSteps(self, N):
		if N == 1:
			return 0
		if self.memo[N] != -1:
			return self.memo[N]
		ans = 100000.0
		if N % 2 == 0:
			ans = min(ans, self.minSteps(N // 2))
		if N % 3 == 0:
			ans = min(ans, self.minSteps(N // 3))
		ans = min(ans, self.minSteps(N - 1))
		self.memo[N] = ans + 1
		return self.memo[N]


class Solution:

	def minSteps(self, n):
		a = [-1 for i in range(n + 1)]
		a[1] = 0
		for i in range(2, n + 1):
			x = a[i - 1]
			y = 1000000
			if i % 2 == 0:
				y = a[i // 2]
			z = 1000000
			if i % 3 == 0:
				z = a[i // 3]
			a[i] = 1 + min(x, y, z)
		return a[n]


class Solution:

	def memo(self, n):
		global dp
		dp = [-1] * (n + 1)

	def soln(self, n):
		if n == 0 or n == 1:
			return 0
		if dp[n] != -1:
			return dp[n]
		a = 10 ** 9 + 7
		b = 10 ** 9 + 7
		c = 10 ** 9 + 7
		if dp[n - 1] != -1:
			a = dp[n - 1]
		else:
			dp[n - 1] = self.soln(n - 1)
			a = dp[n - 1]
		if n % 2 == 0:
			if dp[n // 2] != -1:
				b = dp[n // 2]
			else:
				dp[n // 2] = self.soln(n // 2)
				b = dp[n // 2]
		if n % 3 == 0:
			if dp[n // 3] != -1:
				c = dp[n // 3]
			else:
				dp[n // 3] = self.soln(n // 3)
				c = dp[n // 3]
		dp[n] = 1 + min(a, b, c)
		return dp[n]

	def minSteps(self, N):
		self.memo(N)
		return self.soln(N)


class Solution:

	def minSteps(self, N):
		n = N
		arr = [0, 0, 1, 1]
		if n < 4:
			return arr[n]
		for i in range(4, n + 1):
			x = float('inf')
			y = float('inf')
			if i % 2 == 0:
				x = arr[i // 2]
			if i % 3 == 0:
				y = arr[i // 3]
			z = i - 1
			arr.append(min(x, y, arr[z]) + 1)
		return arr[n]


import sys

class Solution:

	def minstep(self, N, memo):
		if N == 1:
			return 0
		ans1 = sys.maxsize
		if N % 3 == 0:
			if memo[N // 3] == -1:
				ans1 = self.minstep(N // 3, memo)
				memo[N // 3] = ans1
			else:
				ans1 = memo[N // 3]
		ans2 = sys.maxsize
		if N % 2 == 0:
			if memo[N // 2] == -1:
				ans2 = self.minstep(N // 2, memo)
				memo[N // 2] = ans2
			else:
				ans2 = memo[N // 2]
		if memo[N - 1] == -1:
			ans3 = self.minstep(N - 1, memo)
			memo[N - 1] = ans3
		else:
			ans3 = memo[N - 1]
		ans = 1 + min(ans1, ans2, ans3)
		return ans

	def minSteps(self, N):
		memo = []
		for i in range(N + 1):
			memo.append(-1)
		ans = self.minstep(N, memo)
		return ans


class Solution:

	def minSteps(self, N):
		dp = [-1 for _ in range(N + 1)]
		return self.dp(N, dp)

	def dp(self, N, dp):
		if N == 1:
			return 0
		ans1 = sys.maxsize
		if N % 3 == 0:
			if dp[N // 3] == -1:
				ans1 = self.dp(N // 3, dp)
				dp[N // 3] = ans1
			else:
				ans1 = dp[N // 3]
		ans2 = sys.maxsize
		if N % 2 == 0:
			if dp[N // 2] == -1:
				ans2 = self.dp(N // 2, dp)
				dp[N // 2] = ans2
			else:
				ans2 = dp[N // 2]
		if dp[N - 1] == -1:
			ans3 = self.dp(N - 1, dp)
			dp[N - 1] = ans3
		else:
			ans3 = dp[N - 1]
		return 1 + min(ans1, ans2, ans3)


class Solution:

	def minSteps(self, N):
		if N == 1:
			return 0
		elif N == 2:
			return 1
		elif N == 3:
			return 1
		else:
			arr = [0] * (N + 1)
			arr[0] = 100000
			arr[1] = 1
			arr[2] = 1
			arr[3] = 1
			for i in range(4, N + 1):
				arr[i] = arr[i - 1] + 1
				if i % 2 == 0:
					arr[i] = min(arr[i], arr[int(i / 2)] + 1)
				if i % 3 == 0:
					arr[i] = min(arr[i], arr[int(i / 3)] + 1)
			return arr[N]


class Solution:

	def minSteps(self, N):
		state = {}

		def helper(N, state):
			if N == 1:
				return 0
			if N in state:
				return state[N]
			result = helper(N - 1, state)
			if N % 2 == 0:
				result = min(result, helper(N / 2, state))
			if N % 3 == 0:
				result = min(result, helper(N / 3, state))
			state[N] = 1 + result
			return state[N]
		return helper(N, state)


class Solution:

	def minSteps(self, n):
		arr = [0] * (n + 1)
		return minspteps(n, arr)

def minspteps(n, arr):
	if n == 1:
		return 0
	if arr[n] != 0:
		return arr[n]
	op1 = op2 = op3 = 9999999
	if n % 3 == 0:
		op1 = minspteps(n // 3, arr)
	if n % 2 == 0:
		op2 = minspteps(n // 2, arr)
	op3 = minspteps(n - 1, arr)
	arr[n] = min(op1, op2, op3) + 1
	return arr[n]


class Solution:

	def helper(self, n, dp):
		if n == 1:
			return 0
		if dp[n] != -1:
			return dp[n]
		ans = self.helper(n - 1, dp)
		if n % 2 == 0:
			ans = min(ans, self.helper(n // 2, dp))
		if n % 3 == 0:
			ans = min(ans, self.helper(n // 3, dp))
		dp[n] = 1 + ans
		return dp[n]

	def minSteps(self, N):
		dp = [-1] * (max(N, 4) + 1)
		dp[1] = 1
		(dp[2], dp[3]) = (1, 1)
		return self.helper(N, dp)


def dpi(i, mem):
	if i in mem:
		return mem[i]
	if i == 1:
		return 0
	elif i % 3 == 0:
		ans = min(1 + dpi(i // 3, mem), 1 + dpi(i - 1, mem))
		mem[i] = ans
	elif i % 2 == 0:
		ans = min(1 + dpi(i // 2, mem), 1 + dpi(i - 1, mem))
		mem[i] = ans
	else:
		ans = 1 + dpi(i - 1, mem)
		mem[i] = ans
	return ans

class Solution:

	def minSteps(self, N):
		mem = {}
		return dpi(N, mem)


def mins(N, lst):
	if N == 2:
		return 1
	else:
		ans = min()
	return lst

class Solution:

	def minSteps(self, N):
		dp = [0 for i in range(N + 1)]
		dp[1] = 0
		for i in range(2, N + 1):
			if i % 3 == 0:
				dp[i] = min(1 + dp[i // 3], 1 + dp[i - 1])
			elif i % 2 == 0:
				dp[i] = min(1 + dp[i // 2], 1 + dp[i - 1])
			else:
				dp[i] = 1 + dp[i - 1]
		return dp[N]


import sys

class Solution:

	def minSteps(self, N):
		dp = [-1] * (N + 1)
		return self.dp(N, dp)

	def dp(self, N, dp):
		if N == 1:
			return 0
		ans1 = sys.maxsize
		if N % 3 == 0:
			if dp[N // 3] == -1:
				ans1 = self.dp(N // 3, dp)
				dp[N // 3] = ans1
			else:
				ans1 = dp[N // 3]
		ans2 = sys.maxsize
		if N % 2 == 0:
			if dp[N // 2] == -1:
				ans2 = self.dp(N // 2, dp)
				dp[N // 2] = ans2
			else:
				ans2 = dp[N // 2]
		if dp[N - 1] == -1:
			ans3 = self.dp(N - 1, dp)
			dp[N - 1] = ans3
		else:
			ans3 = dp[N - 1]
		return 1 + min(ans1, ans2, ans3)


from collections import deque

class Solution:

	def minSteps(self, N):
		step = 0
		q = deque([(N, step)])
		while q:
			(curr, steps) = q.popleft()
			if curr == 1:
				return steps
			if curr % 2 == 0:
				q.append((curr // 2, steps + 1))
			if curr % 3 == 0:
				q.append((curr // 3, steps + 1))
			q.append((curr - 1, steps + 1))