#include <bits/stdc++.h>
#define int long long
#define N 11
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
struct dat{
  int x,y,X,Y;
  bool contain(dat b){return (x<=b.x && b.X<=X) && (y<=b.y && b.Y<=Y);}
};

int h,w;
vector<dat> A;
typedef vector<vector<int> > V;


int count(const V &mp,dat a){
  int cnt = 0;
  for(int i=a.y;i<=a.Y;i++) cnt += count(mp[i].begin()+a.x,mp[i].begin()+a.X+1,1);
  return cnt;
}

bool contain0(V &mp,int x,int y,int X,int Y){return count(mp,(dat){x,y,X,Y}) == (X-x+1)*(Y-y+1);}

struct dat2{
  V mp;
  int cnt,cost;
};

dat2 getNx(dat2 t,dat a){
  t.cost++;
  for(int i=a.y;i<=a.Y;i++)
    for(int j=a.x;j<=a.X;j++){
      t.cnt -= t.mp[i][j];
      t.mp[i][j] = 0;
    }
  return t;
}

dat2 erase(dat2 t){
  int update = 1;
  while(update--){
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++){
        if(t.mp[i][j] == 0)continue;
        int cnt = 0;
        dat tmp;
        for(dat a:A) if(a.contain((dat){j,i,j,i})) cnt++, tmp = a;
        if(cnt == 1) t = getNx(t,tmp),update = 1;
      }
  }
  return t;
}

typedef pair<int,int> P;
set<P> getErased(const V &mp,const dat &a){
  set<P> res;
  for(int i=a.y;i<=a.Y;i++)
    for(int j=a.x;j<=a.X;j++)
      if(mp[i][j]) res.insert(P(i,j));
  return res;
}

int bfs(V start){
  queue<dat2> Q;
  set<V> used;
  Q.push((dat2){start,count(start,(dat){0,0,w-1,h-1}),0});

  while(1){
    dat2 t = erase(Q.front());Q.pop();
    if(t.cnt == 0) return t.cost;
    if(used.count(t.mp))continue;
    used.insert(t.mp);

    dat nx;
    for(dat a:A) if(count(t.mp,a)) nx = a;
    set<P> S = getErased(t.mp,nx);
    for(dat a:A){
      set<P> s = getErased(t.mp,a);
      int cnt = 0;
      for(P p:s) cnt += S.count(p);
      if(cnt) Q.push(getNx(t,a));
    }
  }
}

signed main(){
  while(1){
    cin>>w>>h;
    if(w == 0 && h == 0)break;

    V mp = V(h,vector<int>(w));
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++) cin>>mp[i][j];
    
    A.clear();
    for(int y=0;y<h;y++)
      for(int x=0;x<w;x++){
        dat a = (dat){-1,-1,-1,-1};
        for(int Y=y, X=x; Y<h && X<w ;Y++, X++) if(contain0(mp,x,y,X,Y)) a = (dat){x,y,X,Y};
        if(a.x != -1) A.push_back(a);
      }
    
    for(int i=0;i<(int)A.size();i++)
      for(int j=0;j<(int)A.size();j++) if(i!=j && A[i].contain(A[j]))A.erase(A.begin()+j--);
    cout<<bfs(mp)<<endl;
  }
  return 0;
}