#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct carpet {
    int y, x;
    int len;
    bool use;
    carpet(int y, int x, int len) : y(y), x(x), len(len), use(true) {}
};

bool contain(carpet const& c1, carpet const& c2) {
    const int lx1 = c1.x, ly1 = c1.y;
    const int lx2 = c2.x, ly2 = c2.y;
    const int len1 = c1.len, len2 = c2.len;
    return lx1 <= lx2 && ly1 <= ly2 && 
           lx2 + len2 <= lx1 + len1 && ly2 + len2 <= ly1 + len1;
}

bool check_clear(vector<vector<int>> const& fld) {
    const int H = fld.size(), W = fld[0].size();
    for(int i = 0; i < H; ++i) {
        for(int j = 0; j < W; ++j) {
            if(fld[i][j] == 1) return false;
        }
    }
    return true;
}

int main() {
    int W, H;
    while(cin >> W >> H, W) {
        vector<vector<int>> fld(H, vector<int>(W));
        for(int i = 0; i < H; ++i) {
            for(int j = 0; j < W; ++j) {
                cin >> fld[i][j];
            }
        }

        auto can_put = [&](int y, int x, int len) {
            if(y + len > H || x + len > W) return false;
            bool res = true;
            for(int i = y; i < y + len; ++i) {
                for(int j = x; j < x + len; ++j) {
                    res &= fld[i][j] == 1;
                }
            }
            return res;
        };

        vector<carpet> cs;
        for(int i = 0; i < H; ++i) {
            for(int j = 0; j < W; ++j) {
                if(fld[i][j] == 1) {
                    int lb = 1, ub = max(H, W) + 1;
                    while(ub - lb > 1) {
                        const int mid = (ub + lb) / 2;
                        if(can_put(i, j, mid)) lb = mid;
                        else                   ub = mid;
                    }
                    cs.emplace_back(i, j, lb);
                }
            }
        }

        int n = cs.size();
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i == j) continue;
                if(contain(cs[i], cs[j])) {
                    cs[j].use = false;
                }
            }
        }

        auto remove_unuse = [&]() {
            cs.erase(remove_if(begin(cs), end(cs), [&](const auto& c) { return !c.use; }), end(cs));
            n = cs.size();
        };
        remove_unuse();

        int ans = 0;
        bool update = true;
        while(update) {
            update = false;

            vector<vector<vector<int>>> v(H, vector<vector<int>>(W));
            for(int i = 0; i < n; ++i) {
                for(int j = cs[i].y; j < cs[i].y + cs[i].len; ++j) {
                    for(int k = cs[i].x; k < cs[i].x + cs[i].len; ++k) {
                        v[j][k].push_back(i);
                    }
                }
            }

            bool update2 = true;
            while(update2) {
                update2 = false;
                for(int i = 0; i < H; ++i) {
                    for(int j = 0; j < W; ++j) {
                        if(v[i][j].size() == 1 && fld[i][j] == 1) {
                            const int idx = v[i][j][0];
                            cs[idx].use = false;
                            update = update2 = true;
                            ans += 1;
                            for(int k = cs[idx].y; k < cs[idx].y + cs[idx].len; ++k) {
                                for(int l = cs[idx].x; l < cs[idx].x + cs[idx].len; ++l) {
                                    v[k][l].erase(find(begin(v[k][l]), end(v[k][l]), idx));
                                    fld[k][l] = 0;
                                }
                            }
                        }
                    }
                }
            }
            remove_unuse();


            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    if(i == j) continue;
                    if(!cs[i].use || !cs[j].use) continue;
                    vector<int> vs1, vs2;
                    for(int y = cs[i].y; y < cs[i].y + cs[i].len; ++y) {
                        for(int x = cs[i].x; x < cs[i].x + cs[i].len; ++x) {
                            if(fld[y][x] == 1) {
                                vs1.push_back(y * W + x);
                            }
                        }
                    }
                    for(int y = cs[j].y; y < cs[j].y + cs[j].len; ++y) {
                        for(int x = cs[j].x; x < cs[j].x + cs[j].len; ++x) {
                            if(fld[y][x] == 1) {
                                vs2.push_back(y * W + x);
                            }
                        }
                    }
                    bool f = true;
                    for(int i = 0; i < (int)vs2.size(); ++i) {
                        f &= find(begin(vs1), end(vs1), vs2[i]) != end(vs1);
                    }
                    if(f) {
                        cs[j].use = false;
                        update = true;
                    }
                }
            }
            remove_unuse();
        }

        int add = 1000;
        for(int S = 0; S < (1 << n); ++S) {
            if(__builtin_popcount(S) >= add) continue;
            auto fld2 = fld;
            for(int i = 0; i < n; ++i) {
                if(S & (1LL << i)) {
                    for(int j = cs[i].y; j < cs[i].y + cs[i].len; ++j) {
                        for(int k = cs[i].x; k < cs[i].x + cs[i].len; ++k) {
                            fld2[j][k] -= 1;
                        }
                    }
                }
            }
            if(check_clear(fld2)) {
                add = min(add, __builtin_popcount(S));
            }
        }

        cout << ans + add << endl;
    }
}



Measured memory_bytes: 3064