Given two numbers M and N, which represents the length and breadth of a paper, the task is to cut the paper into squares of any size and find the minimum number of squares that can be cut from the paper.
Example 1:
Input: M = 36, N = 30
Output: 5
Explanation: 
3 (squares of size 12x12) + 
2 (squares of size 18x18)
Example 2:
Input: M = 4, N = 5
Output: 5
Explanation: 
1 (squares of size 4x4) + 
4 (squares of size 1x1)
Your Task:  
You don't need to read input or print anything. Complete the function minCut() which takes M and N as input parameters and returns the integer value
Expected Time Complexity: O(M*N*(N +M))
Expected Auxiliary Space: O(M*N)
Constraints:
1 ≤ M, N ≤ 10^{2}

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(M*N*(N +M))
Expected Auxiliary Space: O(M*N)

Starter code:
#User function Template for python3

class Solution:

	def minCut(self, M, N):

		# code here

Solutions:
import sys

class Solution:

	def get(self, m, n, dp):
		if m == n:
			return 1
		if dp[m][n] != -1:
			return dp[m][n]
		ans = sys.maxsize
		for i in range(1, m // 2 + 1):
			ans = min(ans, self.get(i, n, dp) + self.get(m - i, n, dp))
		for i in range(1, n // 2 + 1):
			ans = min(ans, self.get(m, i, dp) + self.get(m, n - i, dp))
		dp[m][n] = ans
		return dp[m][n]

	def minCut(self, m, n):
		dp = []
		for i in range(0, m + 1):
			dp.append([-1] * (n + 1))
		return self.get(m, n, dp)


class Solution:

	def minCut(self, M, N):
		dp = [[float('inf') for _ in range(N)] for _ in range(M)]
		for i in range(N):
			dp[0][i] = i + 1
		for i in range(M):
			dp[i][0] = i + 1
		for i in range(min(N, M)):
			dp[i][i] = 1
		for i in range(M):
			for j in range(N):
				for k in range(i):
					dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k - 1][j])
				for k in range(j):
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k - 1])
		return dp[-1][-1]


class Solution:

	def minCut(self, N, M):
		dp = [[0 for i in range(M + 1)] for j in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, M + 1):
				if i == j:
					dp[i][j] = 0
				else:
					res1 = res2 = int(1000000000.0 + 7)
					for k in range(1, i):
						res1 = min(res1, dp[k][j] + dp[i - k][j])
					for k in range(1, j):
						res2 = min(res2, dp[i][k] + dp[i][j - k])
					dp[i][j] = min(res1, res2) + 1
		return dp[N][M] + 1


class Solution:

	def minCut(self, M, N):
		dp = [[float('inf') for _ in range(N + 1)] for _ in range(M + 1)]
		for i in range(M + 1):
			for j in range(N + 1):
				if i == 0 and j == 0:
					dp[i][j] = 0
				elif i == 0:
					dp[i][j] = j
				elif j == 0:
					dp[i][j] = i
				elif i == j:
					dp[i][j] = 1
				else:
					for x in range(0, i + 1):
						dp[i][j] = min(dp[i][j], dp[i - x][j] + dp[x][j])
					for x in range(0, j + 1):
						dp[i][j] = min(dp[i][j], dp[i][j - x] + dp[i][x])
		return dp[M][N]


class Solution:

	def minCut(self, M, N):
		dp = dict()

		def rec(m, n):
			if m == 0 or n == 0:
				return 0
			if m == n:
				return 1
			if (m, n) not in dp:
				ans = 1000000000000000.0
				mini = min(m, n)
				for i in range(1, mini + 1):
					x = rec(m - i, i)
					y = rec(i, n - i)
					z = rec(m - i, n - i)
					p = rec(m, n - i)
					q = rec(m - i, n)
					ans = min(ans, x + y + z + 1, p + x + 1, q + y + 1)
				dp[m, n] = ans
			return dp[m, n]
		return rec(M, N)


class Solution:

	def minCut(self, M, N):
		dp = [[float('inf') for i in range(101)] for j in range(101)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == j:
					dp[i][j] = 1
				elif i == 1:
					dp[i][j] = j
				elif j == 1:
					dp[i][j] = i
				elif i == 0 or j == 0:
					dp[i][j] = 0
				else:
					for k in range(i + 1):
						dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j])
					for k in range(j + 1):
						dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k])
		return dp[m][n]


class Solution:

	def minCut(self, M, N):
		memo = {}

		def cut_paper(n, m):
			if n < 1 or m < 1:
				return 0
			key = (n, m)
			rev_key = (m, n)
			if key in memo:
				return memo[key]
			if n == 1 or m == 1:
				memo[key] = max(n, m)
				memo[rev_key] = memo[key]
				return memo[key]
			if n == m:
				memo[key] = 1
				return memo[key]
			cur_result = 1 << 31
			for i in range(1, n // 2 + 1):
				ans = cut_paper(i, m) + cut_paper(n - i, m)
				cur_result = min(cur_result, ans)
			for j in range(1, m // 2 + 1):
				ans = cut_paper(n, j) + cut_paper(n, m - j)
				cur_result = min(cur_result, ans)
			memo[key] = cur_result
			memo[rev_key] = cur_result
			return memo[key]
		return cut_paper(M, N)


class Solution:

	def minCutUtil(self, m, n, dp):
		vertical_min = float('inf')
		horizontal_min = float('inf')
		if m == n:
			return 1
		if dp[m][n] != -1:
			return dp[m][n]
		for i in range(1, m // 2 + 1):
			horizontal_min = min(self.minCutUtil(i, n, dp) + self.minCutUtil(m - i, n, dp), horizontal_min)
		for j in range(1, n // 2 + 1):
			vertical_min = min(self.minCutUtil(m, j, dp) + self.minCutUtil(m, n - j, dp), vertical_min)
		dp[m][n] = min(vertical_min, horizontal_min)
		return dp[m][n]

	def minCut(self, m, n):
		dp = [[-1] * (n + 1) for i in range(m + 1)]
		return self.minCutUtil(m, n, dp)


class Solution:

	def minCut(self, m, n):
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]

		def minimumSquare(m, n):
			vertMin = float('inf')
			horiMin = float('inf')
			if m == n:
				return 1
			if dp[m][n] != 0:
				return dp[m][n]
			for i in range(1, m // 2 + 1):
				horiMin = min(horiMin, minimumSquare(i, n) + minimumSquare(m - i, n))
			for j in range(1, n // 2 + 1):
				vertMin = min(vertMin, minimumSquare(m, j) + minimumSquare(m, n - j))
			dp[m][n] = min(horiMin, vertMin)
			return dp[m][n]
		ans = minimumSquare(m, n)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(m, n) = input().split()
		(m, n) = (int(m), int(n))
		ob = Solution()
		ans = ob.minCut(m, n)
		print(ans)


class Solution:

	def cache(self, r, c, val):
		self.cut_cache[r][c] = val
		if r < self.N and c < self.M:
			self.cut_cache[c][r] = val
		return val

	def minCutRec(self, M, N):
		if self.cut_cache[M][N] != None:
			return self.cut_cache[M][N]
		if M == 1:
			return self.cache(M, N, N)
		if N == 1:
			return self.cache(M, N, M)
		if M % N == 0:
			return self.cache(M, N, M // N)
		if N % M == 0:
			return self.cache(M, N, N // M)
		min_cuts = 9999999999999
		for i in range(1, M - 1):
			cuts = self.minCutRec(i, N) + self.minCutRec(M - i, N)
			min_cuts = min(min_cuts, cuts)
		for i in range(1, N - 1):
			cuts = self.minCutRec(M, i) + self.minCutRec(M, N - i)
			min_cuts = min(min_cuts, cuts)
		return self.cache(M, N, min_cuts)

	def minCut(self, M, N):
		self.M = M
		self.N = N
		self.cut_cache = [[None] * (N + 1) for _ in range(M + 1)]
		return self.minCutRec(M, N)


class Solution:

	def minCut(self, M, N):
		d = [[-1 for x in range(N + 1)] for y in range(M + 1)]

		def recur(i, j):
			if i == j:
				return 1
			if d[i][j] != -1:
				return d[i][j]
			res = float('inf')
			for x in range(1, i):
				res = min(res, recur(i - x, j) + recur(x, j))
			for x in range(1, j):
				res = min(res, recur(i, j - x) + recur(i, x))
			d[i][j] = res
			return res
		return recur(M, N)


from functools import lru_cache

class Solution:

	@lru_cache(maxsize=1000000)
	def dp(self, m, n):
		ans = 10000000000
		if m == n:
			return 1
		for i in range(1, m):
			ans = min(ans, self.dp(i, n) + self.dp(m - i, n))
		for i in range(1, n):
			ans = min(ans, self.dp(m, i) + self.dp(m, n - i))
		return ans

	def minCut(self, M, N):
		return self.dp(M, N)


class Solution:

	def minCut(self, M, N):
		history = [[float('inf')] * (N + 1) for i in range(M + 1)]
		for i in range(M):
			for j in range(N):
				if i == j:
					history[i][j] = 1

		def helper(M, N):
			if N < 0 or M < 0:
				return float('inf')
			if history[M - 1][N - 1] != float('inf'):
				return history[M - 1][N - 1]
			min_count = float('inf')
			if M > 1:
				for i in range(1, M):
					min_count = min(min_count, helper(M - i, N) + helper(i, N))
			if N > 1:
				for i in range(1, N):
					min_count = min(min_count, helper(M, N - i) + helper(M, i))
			history[M - 1][N - 1] = min_count
			return min_count
		return helper(M, N)


class Solution:

	def minCut(self, M, N):
		self.cache = dict()
		return self.min_squares(m, n)

	def min_squares(self, m, n):
		if m == n:
			return 1
		if (m, n) in self.cache:
			return self.cache[m, n]
		x = 2 ** 32
		for i in range(1, n // 2 + 1):
			x = min(x, self.min_squares(m, i) + self.min_squares(m, n - i))
		for i in range(1, m // 2 + 1):
			x = min(x, self.min_squares(i, n) + self.min_squares(m - i, n))
		self.cache[m, n] = x
		return x


class Solution:

	def minCut(self, M, N):
		dp = [[10000.0] * (M + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for j in range(M + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				if i == 1:
					dp[i][j] = j
				elif j == 1:
					dp[i][j] = i
				elif i == j:
					dp[i][j] = 1
				else:
					for k in range(i):
						dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j])
					for k in range(j):
						dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k])
		return dp[N][M]


def minSquare(m, n):
	global dp
	try:
		return dp[m, n]
	except:
		pass
	if m <= 0 or n <= 0:
		return 0
	if m == 1:
		return n
	if n == 1:
		return m
	res = float('inf')
	for i in range(1, min(m, n) + 1):
		k1 = minSquare(m, n - i) + minSquare(m - i, i)
		k2 = minSquare(i, n - i) + minSquare(m - i, n)
		res = min(res, min(k1, k2))
	dp[m, n] = 1 + res
	return dp[m, n]

def controllerMinSquare(m, n):
	global dp
	dp = {}
	return minSquare(m, n)

class Solution:

	def minCut(self, M, N):
		return controllerMinSquare(M, N)


class Solution:

	def minCut(self, M, N):
		dp = [[0 for i in range(N + 1)] for _ in range(M + 1)]
		for j in range(1, N + 1):
			dp[1][j] = j
		for i in range(2, M + 1):
			for j in range(1, N + 1):
				dp[i][j] = 10 ** 5
				if i == j:
					dp[i][j] = 1
				else:
					for k in range(1, min(i + 1, j + 1)):
						dp[i][j] = min(dp[i][j], 1 + dp[i - k][j] + dp[k][j - k], 1 + dp[i][j - k] + dp[i - k][k])
		return dp[M][N]


class Solution:

	def minCut(self, M, N):
		m = M
		n = N
		dp = [[n * m] * (m + 1) for _ in range(n + 1)]
		dp[0][0] = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if i == j:
					dp[i][j] = 0
					continue
				if j > 1:
					for k in range(1, j):
						dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k] + 1)
				if i > 1:
					for k in range(1, i):
						dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j] + 1)
		return dp[n][m] + 1


import sys

class Solution:

	def minCut(self, M, N):
		(M, N) = (min(M, N), max(M, N))
		DP = [[sys.maxsize] * (N + 1) for _ in range(0, M + 1)]
		DP[0] = [0] * (N + 1)
		for m in range(1, M + 1):
			for n in range(1, N + 1):
				if m > n:
					continue
				elif m == n:
					DP[m][n] = 1
				else:
					for i in range(1, n // 2 + 1):
						(fore_y, fore_x) = (min(m, i), max(m, i))
						(rear_y, rear_x) = (min(m, n - i), max(m, n - i))
						fore_val = DP[fore_y][fore_x]
						rear_val = DP[rear_y][rear_x]
						DP[m][n] = min(DP[m][n], fore_val + rear_val)
					for i in range(1, m // 2 + 1):
						(fore_y, fore_x) = (min(n, i), max(n, i))
						(rear_y, rear_x) = (min(n, m - i), max(n, m - i))
						fore_val = DP[fore_y][fore_x]
						rear_val = DP[rear_y][rear_x]
						DP[m][n] = min(DP[m][n], fore_val + rear_val)
		return DP[M][N]


class Solution:
	squares = [[0 for _ in range(101)] for _ in range(101)]

	def minCut(self, m, n):
		if m == n:
			return 1
		if self.squares[m][n] != 0:
			return self.squares[m][n]
		horizontal_min = float('inf')
		for i in range(1, m // 2 + 1):
			horizontal_min = min(self.minCut(i, n) + self.minCut(m - i, n), horizontal_min)
		vertical_min = float('inf')
		for i in range(1, n // 2 + 1):
			vertical_min = min(self.minCut(m, i) + self.minCut(m, n - i), vertical_min)
		self.squares[m][n] = min(horizontal_min, vertical_min)
		return self.squares[m][n]