#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int H, W;
bitset<100> field;
bitset<100> zeros;
int carpet[15][15];
int baseans;
int ans;
vector<bitset<100>> bits;

void print(bitset<100> a) {
    for(int h = 0; h < H; h++) {
        for(int w = 0; w < W; w++) {
            cerr << a[h*10+w];
        }
        cerr << endl;
    }
}

void dfs(int index, int nowans, bitset<100> nowfield) {
    if(index == bits.size()) {
        if(nowfield == (~zeros)) {
            ans = min(ans, nowans);
        }
        return;
    }
    dfs(index + 1, nowans, nowfield);
    dfs(index + 1, nowans + 1, nowfield |= bits[index]);
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(true) {
        bits.clear();
        baseans = 0;
        ans = INF;
        cin >> W >> H;
        if(H == 0) break;
        for(int h = 0; h < H; h++) {
            for(int w = 0; w < W; w++) {
                cin >> carpet[h][w];
            }
        }
        field &= zeros;
        /*
        for(int h = H; h < 10; h++) {
            for(int w = W; w < 10; w++) {
                field[h * 10 + w] = true;
            }
        }*/
        for(int h = 0; h < 10; h++) {
            for(int w = 0; w < 10; w++) {
                if(h >= H || w >= W) {
                    field[h * 10 + w] = true;
                    continue;
                }
                if(carpet[h][w] == 0) field[h * 10 + w] = true;
            }
        }
        for(int h = 0; h < H; h++) {
            for(int w = 0; w < W; w++) {
                if(carpet[h][w] == 0) continue;
                int SIZE = 1;
                while(true) {
                    //cerr << h << " " << w << " " << SIZE << endl;
                    if(h + SIZE == H) break;
                    if(w + SIZE == W) break;
                    bool ok = true;
                    for(int noww = w; noww <= w + SIZE; noww++) {
                        if(carpet[h+SIZE][noww] == 0) ok = false;
                    }
                    for(int nowh = h; nowh <= h + SIZE; nowh++) {
                        if(carpet[nowh][w+SIZE] == 0) ok = false;
                    }
                    if(!ok) break;
                    SIZE++;
                }
                bitset<100> now;
                for(int nowh = h; nowh < h + SIZE; nowh++) {
                    for(int noww = w; noww < w + SIZE; noww++) {
                        now[nowh * 10 + noww] = true;
                    }
                }
                bits.push_back(now);
            }
        }
        for(int timer = 0; timer <= 10; timer++) {
        for(int i = 0; i < bits.size(); i++) {
            //cerr << i << endl;
            for(int j = 0; j < bits.size(); j++) {
                if(i == j) continue;
                if((bits[i] & bits[j]) == bits[i]) {
                    //cerr << i << " " << bits[i] << endl;
                    //cerr << j << " " << bits[j] << endl;
                    bits.erase(bits.begin() + i);
                    i--;
                    break;
                }
            }
        }
        for(int i = 0; i < bits.size(); i++) {
            //cerr << endl << i << endl;
            //print(bits[i]);
        }
        for(int i = 0; i < bits.size(); i++) {
            //cerr << "others " << i << endl;
            bitset<100> others;
            for(int j = 0; j < bits.size(); j++) {
                if(i == j) continue;
                others |= bits[j];
            }
            if((bits[i] | others) != others) {
                field |= bits[i];
                for(int k = 0; k < bits.size(); k++) {
                    if(i == k) continue;
                    bits[k] &= (~bits[i]);
                }
                baseans++;
                bits.erase(bits.begin() + i);
                i--;
                continue;
            }
        }
        }
        /*
        cerr << baseans << endl;
        for(int i = 0; i < bits.size(); i++) cerr << bits[i] << endl;
        */
        for(int i = 0; i < bits.size(); i++) {
            if(bits[i] == zeros) {
                bits.erase(bits.begin() + i);
                i--;
            }
        }
        //cerr << baseans << endl;
        //cerr << bits.size() << endl;
        //print(field);
        //cerr << field << endl;
        dfs(0, 0, field);
        cout << ans + baseans << endl;
    }
    return 0;
}


Measured memory_bytes: 3176