Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.
 
Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)
Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

 
Constraints:

1 <= n <= 13
1 <= m <= 13

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "import functools\nclass Solution:\n    def tilingRectangle(self, n: int, m: int) -> int:\n        # 谷歌面经。给定你一个矩形。问你最少需要多少个正方形来填满。\n        '''\n        INF = n * m\n        \n        @functools.lru_cache(None)\n        def dp(state):   # state是一个tuple, m个元素\n            if n == min(state):\n                return 0\n            \n            state = list(state)   # 从左到右铺\n            mn = min(state)\n            start = state.index(mn)\n            res = INF\n            for end in range(start,m):\n                if state[end] != mn:\n                    break\n                side = end - start + 1\n                if mn + side > n:\n                    break\n                state[start:end + 1] = [mn + side] * side\n                res = min(res, dp(tuple(state)))\n            return res + 1\n\n        if m > n:   # 保证n大,保证高度最大宽度其次\n            m, n = n, m\n        return dp(tuple([0] * m))   # tuple做state\n        '''\n        '''\n        self.res = m * n\n        def dfs(height, moves):\n            if all(h == n for h in height):\n                self.res = min(self.res, moves)\n            if moves >= self.res:  # 剪枝\n                return \n            min_height = min(height)\n            idx = height.index(min_height)\n            ridx = idx + 1\n            while ridx < m and height[ridx] == min_height:  # 找到了一个最大的范围\n                ridx += 1\n            for i in range(min(ridx - idx, n - min_height), 0, -1):\n                new_height = height[:]\n                for j in range(i):\n                    new_height[idx + j] += i\n                dfs(new_height, moves + 1)\n        dfs([0] * m, 0)  # dfs的是目前的状态以及导致目前状态的操作步骤数\n        return self.res\n        '''\n        '''\n        # A* algrithm\n        height = [0] * m\n        q = []\n        for i in range(min(m, n), 0, -1):\n            # push to heap: (guess, moves, -size, height)\n            heapq.heappush(q, (1, 1, -i, height)) # 这里的height是size还没用,待处理的\n        \n        while q:\n            guess, moves, neg_size, height = heapq.heappop(q)\n            size = -neg_size\n            \n            idx = height.index(min(height))  # 默认操作从左侧最低的位置装\n            height = height[:]    # 如果最小堆tuple弹出里有数组，用的时候，先把数组全部取一下[:]\n            for i in range(size):\n                height[idx + i] += size\n            if all(h == n for h in height):\n                return moves\n            \n            min_height = min(height)\n            idx = height.index(min_height)\n            ridx = idx + 1\n            while ridx < m and height[ridx] == min_height:\n                ridx += 1\n            for i in range(min(ridx - idx, n - min_height), 0, -1):\n                t = moves + 1 + len(set(h for h in height if h < n))\n                heapq.heappush(q, (t, moves + 1, -i, height))\n        '''\n        '''\n        total_area = m * n\n        dp = [0] * (total_area + 1) # 使用dp的方法去(猜测)目前最少需要多少个square填满\n        for i in range(1, total_area + 1):\n            dp[i] = 1 + min(dp[i - k ** 2] for k in range(1, int(i ** 0.5) + 1))\n        \n        height = [0] * m\n        q = []\n        for i in range(min(m, n), 0, -1):\n            heapq.heappush(q, (1 + dp[total_area - i ** 2], 1, i, height))\n        \n        while q:\n            guess, moves, size, height = heapq.heappop(q)\n            \n            idx = height.index(min(height))\n            height = height[:]\n            for i in range(size):\n                height[idx + i] += size   #这里不能把i写成1\n            if all(h == n for h in height):\n                return moves\n            \n            min_height = min(height)\n            idx = height.index(min_height)\n            ridx = idx + 1\n            while ridx < m and height[ridx] == min_height:\n                ridx += 1\n            for i in range(min(ridx - idx, n - min_height), 0, -1):\n                guess = dp[total_area - sum(height) - i ** 2]\n                heapq.heappush(q, (guess + 1 + moves, moves + 1, i, height))\n        '''\n        # 仔细观察题目,可以发现其实一个矩形就是三种切法。横切竖切以及中间矩形分割。\n        # 对于中间矩形分割，只要知道矩形的位置和大小，那么周围的四个矩形就可以求出来。\n        @lru_cache(None)\n        def dfs(i, j):\n            # corner case\n            if i == j:\n                return 1\n            if i == 1:\n                return j\n            if j == 1:\n                return i\n            \n            res = i * j     # 最多也就x*y这么多个，作为最大值先赋res\n            for x in range(1, i // 2 + 1):\n                res = min(res, dfs(x, j) + dfs(i - x, j))\n            for y in range(1, j // 2 + 1):\n                res = min(res, dfs(i, y) + dfs(i, j - y))\n            \n            #https://blog.csdn.net/qq_17550379/article/details/102787329?ops_request_misc=&request_id=&biz_id=102&utm_term=leetcode%E9%93%BA%E7%93%B7%E7%A0%96&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-102787329\n            for leng in range(1, min(x, y)):  # 中间正方形的大小\n                for x in range(1, i - leng):    # 正方形的左上角位置,保证不会贴合四个大边\n                    for y in range(1, j - leng):\n                        res = min(res, dfs(x + leng, y) + dfs(i - (x + leng), y + leng) + dfs(x, j - y) + dfs(i - x, j - (y + leng)) + 1)\n            return res\n        return dfs(m, n) # dfs矩形大小，用长宽两个变量来表示"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'tilingRectangle'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 8468