#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <list>
#include <cmath>
#include <iomanip>
#define INF 0x3f3f3f3f
#define EPS 10e-5

typedef long long ll;
const int dx[]={-1,0,0,1,0},dy[]={0,1,-1,0,0};
using namespace std;
int w,h,ecnt;
int mps[10][10];    // record used square
int cnts[10][10][2];// record the square size
int scts[10][10];
bool badc[10][10];
int upbound,bcnt,mxsqus,res;
bool reach,needf[10][10];

int vps[250];
int vsct[250][250],vl[250];

void dfs(int now,int cost){

    if(ecnt==0) {
        if(cost==res)
            reach = true;
        upbound = min(upbound,cost);
        return;
    }

    if(cost+round(1.0*ecnt/mxsqus)>res||reach) return;

    if(now==bcnt) return;

    bool cover = false;
    int bs = vl[now],*vct=vsct[now];

    for(int i=0;i<bs;++i){
        if(vps[vct[i]]==0){
            cover = true;break;
        }
    }

    if(!cover) {
        return dfs(now+1,cost);
    }

    for(int i=0;i<bs;++i){
        if(++vps[vct[i]]==1) --ecnt;
    }
    dfs(now+1,cost+1);
    for(int i=0;i<bs;++i){
        if(--vps[vct[i]]==0) ++ecnt;
    }

    if(vps[vsct[now][0]]==0) return;
    dfs(now+1,cost);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    while(scanf("%d%d",&w,&h)){
        if(w==0&&h==0)break;
        memset(mps,0,sizeof(mps));
        memset(cnts,0,sizeof(cnts));
        memset(badc,0,sizeof(badc));
        memset(needf,0,sizeof(needf));
        memset(vl,0,sizeof(vl));

        ecnt = mxsqus = 0;
        int tmp;
        for(int i=0;i<h;++i)
            for(int j=0;j<w;++j){
                scanf("%d",&tmp);
                if(tmp) {
                    mps[i][j] = 1;++ecnt;
                    needf[i][j] = true;
                }
            }
        if(ecnt==0){
            printf("0\n");
            continue;
        }
        for(int i=0;i<w;++i){
            int last = 0;
            for(int j=h-1;j>=0;--j){
                if(mps[j][i]) cnts[j][i][1] = ++last;
                else last = 0;
            }
        }
        for(int i=0;i<h;++i)
        {
            int last = 0;
            for(int j=w-1;j>=0;--j){
                if(mps[i][j]) cnts[i][j][0] = ++last;
                else last = 0;
            }
        }

        for(int i=0;i<h;++i)
            for(int j=0;j<w;++j)
            {
                int k=j,last = INF;
                for(;k<w;++k){
                    last = min(cnts[i][k][1],last);
                    if(k+1-j>last) break;
                }
                mxsqus = max(scts[i][j] = k-j,mxsqus);
            }
        mxsqus*=mxsqus;
        bcnt = 0;

        for(int i=0;i<h;++i)
            for(int j=0;j<w;++j){
                if(badc[i][j]) continue;
                for(int i2=0;i2<scts[i][j];++i2){
                    for(int j2=0;j2<scts[i][j];++j2){
                        if(i2==0&&j2==0) continue;
                        if(scts[i+i2][j+j2]<=min(scts[i][j]-i2,scts[i][j]-j2)){
                            badc[i+i2][j+j2] = true;
                        }
                    }
                }
            }

        for(int i=0;i<h;++i){
            for(int j=0;j<w;++j){
                if(!badc[i][j]){
                    for(int i2=0;i2<scts[i][j];++i2){
                        for(int j2=0;j2<scts[i][j];++j2){
                            vsct[bcnt][vl[bcnt]++] = (i+i2)*w+j+j2;
                        }
                    }
                    bcnt++;
                }
            }
        }

        memset(mps,0,sizeof(mps));
        upbound = INF;
        res = ecnt/mxsqus;reach = false;
        while(!reach&&res!=upbound){
            dfs(0,0);
            ++res;
        }
        printf("%d\n",upbound);
    }
    return 0;
}



Measured memory_bytes: 3452