<p>Given a rectangle of size <code>n</code> x <code>m</code>, return <em>the minimum number of integer-sided squares that tile the rectangle</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_11_1592.png" style="width: 154px; height: 106px;" /></p>

<pre>
<strong>Input:</strong> n = 2, m = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> <code>3</code> squares are necessary to cover the rectangle.
<code>2</code> (squares of <code>1x1</code>)
<code>1</code> (square of <code>2x2</code>)</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_22_1592.png" style="width: 224px; height: 126px;" /></p>

<pre>
<strong>Input:</strong> n = 5, m = 8
<strong>Output:</strong> 5
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_33_1592.png" style="width: 224px; height: 189px;" /></p>

<pre>
<strong>Input:</strong> n = 11, m = 13
<strong>Output:</strong> 6
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n, m &lt;= 13</code></li>
</ul>

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        # Initialize the minimum number of squares to a large number
        self.min_squares = float('inf')
        
        # Create a grid to keep track of covered areas
        grid = [[0] * m for _ in range(n)]
        
        def is_valid(x, y, size):
            # Check if a square of given size can be placed at (x, y)
            if x + size > n or y + size > m:
                return False
            for i in range(x, x + size):
                for j in range(y, y + size):
                    if grid[i][j] != 0:
                        return False
            return True
        
        def place_square(x, y, size, value):
            # Place or remove a square of given size at (x, y)
            for i in range(x, x + size):
                for j in range(y, y + size):
                    grid[i][j] = value
        
        def backtrack(count):
            # If the current count of squares is already greater than the minimum found, return
            if count >= self.min_squares:
                return
            
            # Find the first uncovered cell
            for i in range(n):
                for j in range(m):
                    if grid[i][j] == 0:
                        # Try placing squares of different sizes
                        for size in range(min(n - i, m - j), 0, -1):
                            if is_valid(i, j, size):
                                place_square(i, j, size, 1)
                                backtrack(count + 1)
                                place_square(i, j, size, 0)
                        return
            
            # If all cells are covered, update the minimum number of squares
            self.min_squares = min(self.min_squares, count)
        
        # Start the backtracking process
        backtrack(0)
        
        return self.min_squares

# Example usage:
solution = Solution()
print(solution.tilingRectangle(2, 3))  # Output: 3
print(solution.tilingRectangle(5, 8))  # Output: 5
print(solution.tilingRectangle(11, 13))  # Output: 6
207