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

struct Carpet {
  int y, x, size;
  bool contain(const auto& c) const {
    if(c.x < x) return false;
    if(x + size < c.x + c.size) return false;
    if(c.y < y) return false;
    if(y + size < c.y + c.size) return false;
    return true;
  }
};

int W, H;
int P[12][12];
int S[12][12];
int L[12][12];

int sum(int y1, int x1, int y2, int x2) {
  return S[y2][x2] - S[y2][x1-1] - S[y1-1][x2] + S[y1-1][x1-1];
}

bool full(auto y1, auto x1, auto y2, auto x2) {
  return sum(y1, x1, y2, x2) == (y2 - y1 + 1) * (x2 - x1 + 1);
};

int greedy() {
  for(auto i = 1; i <= H; ++i) for(auto j = 1; j <= W; ++j) S[i][j] = P[i][j];
  for(auto i = 1; i <= H; ++i) for(auto j = 1; j <= W; ++j) S[i][j] += S[i][j-1];
  for(auto j = 1; j <= W; ++j) for(auto i = 1; i <= H; ++i) S[i][j] += S[i-1][j];

  vector<Carpet> carpet;
  for(auto i = 1; i <= H; ++i) for(auto j = 1; j <= W; ++j) {
    auto size = -1;
    for(auto k = 0; k < 10; ++k) {
      if(H < i+k || W < j+k) break;
      if(!full(i, j, i+k, j+k)) break;
      size = k;
    }
    if(~size) carpet.push_back({i, j, size});
  }

  vector<bool> removed(carpet.size());
  for(auto i = 0; i < carpet.size(); ++i) if(!removed[i]) for(auto j = 0; j < carpet.size(); ++j) if(!removed[j]) if(i != j) if(carpet[i].contain(carpet[j])) removed[j] = true;

  int res = 0;

  vector<vector<int>> cnt(H+2, vector<int>(W+2));
  vector<vector<int>> id(H+2, vector<int>(W+2));
  for(auto k = 0; k < carpet.size(); ++k) if(!removed[k]) {
    auto c = carpet[k];
    for(auto i = c.y; i <= c.y + c.size; ++i) for(auto j = c.x; j <= c.x + c.size; ++j) {
      ++cnt[i][j];
      id[i][j] = k;
    }
  }

  for(auto i = 1; i <= H; ++i) for(auto j = 1; j <= W; ++j) if(cnt[i][j] == 1) if(!removed[id[i][j]]) {
    removed[id[i][j]] = true;
    ++res;
    auto c = carpet[id[i][j]];
    for(auto i = c.y; i <= c.y + c.size; ++i) for(auto j = c.x; j <= c.x + c.size; ++j) P[i][j] = 0;
  }

  for(auto i = 0; i < carpet.size(); ++i) if(!removed[i]) L[carpet[i].y][carpet[i].x] = carpet[i].size + 1;

  return res;
}

bool dfs(int sy, int sx, int depth, int limit) {
  int y, x;
  for(y = sy; y <= H; ++y) {
    for(x = (y==sy ? sx : 1); x <= W; ++x) {
      if(L[y][x]) break;
      if(P[y][x] == 1) return false;
    }
    if(L[y][x]) break;
  }
  if(y == H+1 || x == W+1) return true;
  if(depth > limit) return false;
  int dup[12][12];
  memcpy(dup, P, 12*12*sizeof(int));
  if(P[y][x] == 0) {
    auto ny = y, nx = x + 1;
    if(W < x) {++ny; nx = 1;}
    if(dfs(ny, nx, depth, limit)) return true;
  }
  auto cnt = 0;
  for(auto i = y; i < y + L[y][x]; ++i) for(auto j = x; j < x + L[y][x]; ++j) if(P[i][j] == 1) {
    P[i][j] = 0;
    ++cnt;
  }
  if(cnt == 0) return false;
  if(dfs(y, x, depth + 1, limit)) return true;
  memcpy(P, dup, 12*12*sizeof(int));
  return false;
}

int solve() {
  auto fix = greedy();
  for(auto i = 0; i <= 100; ++i) {
    if(dfs(1, 1, 0, i)) return fix + i;
  }
  assert(false);
}

int main() {
  while(cin >> W >> H, W | H) {
    memset(P, 0, 12*12*sizeof(int));
    memset(S, 0, 12*12*sizeof(int));
    memset(L, 0, 12*12*sizeof(int));
    for(auto i = 1; i <= H; ++i) for(auto j = 1; j <= W; ++j) cin >> P[i][j];
    cout << solve() << endl;
  }
}

Measured memory_bytes: 3172