Use DP over dimensions: dp[i][j] = minimum cuts to split an i×j rectangle into all squares. Base case: when i == j, dp[i][j] = 0 (already a square).

Try every possible cut: for each horizontal cut at k (1 ≤ k < i), dp[i][j] = 1 + dp[k][j] + dp[i - k][j]; for each vertical cut at k (1 ≤ k < j), dp[i][j] = 1 + dp[i][k] + dp[i][j - k]. Take the minimum of all options.

With i, j ≤ 500, O(a * b * (a + b)) DP is feasible. Iterate i from 1 to a, j from 1 to b, and precompute all sub-rectangle results before using them.