// * template

#include <bits/stdc++.h>
#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

using namespace std;

template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

template<class T, class U> inline void fill_array(T &e, const U &v) { e = v; }
template<class T, class U, size_t s> inline void fill_array(T (&a)[s], const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U, size_t s> inline void fill_array(array<T, s> &a, const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U> inline void fill_array(vector<T> &a, const U &v) {for(auto&e:a)fill_array(e,v);}

// * solve

constexpr int MAX_H = 10;
constexpr int MAX_W = 10;

typedef bitset<MAX_H * MAX_W> Bitset;

int w, h;
int ans;

inline int index(const int x, const int y) {
	return x + y * w;
}

void print(const Bitset &b) {
	cout << string(50, '-') << endl;
	for(int i = 0; i < h; ++i) {
		for(int j = 0; j < w; ++j) {
			cout << b[index(j, i)] << ' ';
		}
		cout << endl;
	}
	cout << string(50, '-') << endl;
}

inline void erase_subset(vector<Bitset> &bits) {
	for(int i = static_cast<int>(bits.size()) - 1; i >= 0; --i) {
		for(int j = 0; j < bits.size(); ++j) {
			if(i == j) continue;

			if((bits[i] & bits[j]) == bits[i]) {
				bits.erase(begin(bits) + i);
				break;
			}
		}
	}
}

vector<Bitset> init(const vector<vector<int>> &p) {
	vector<vector<int>> sum(h + 2, vector<int>(w + 2, 0));
	for(int y = 1; y <= h + 1; ++y) {
		for(int x = 1; x <= w + 1; ++x) {
			sum[y][x] = p[y][x] + sum[y - 1][x] + sum[y][x - 1] - sum[y - 1][x - 1];
		}
	}

	const auto calc = [&](int x1, int y1, int x2, int y2) -> int {
		--x1; --y1;
		return x1 < 0 || y1 < 0 ? 0 : sum[y2][x2] - sum[y2][x1] - sum[y1][x2] + sum[y1][x1];
	};

	vector<Bitset> carpets;
	for(int y = 1; y <= h; ++y) {
		for(int x = 1; x <= w; ++x) {
			if(p[y][x] == 0) continue;

			for(int dx : {-1, 1}) {
				for(int dy : {-1, 1}) {
					int cx = x, cy = y;
					while(true) {
						const int min_x = min(x, cx + dx);
						const int min_y = min(y, cy + dy);
						const int max_x = max(x, cx + dx);
						const int max_y = max(y, cy + dy);

						if(calc(min_x, min_y, max_x, max_y) < (max_x - min_x + 1) * (max_y - min_y + 1)) {
							break;
						}

						cx += dx;
						cy += dy;
					}

					Bitset tmp;
					for(int i = min(y, cy); i <= max(y, cy); ++i) {
						for(int j = min(x, cx); j <= max(x, cx); ++j) {
							tmp[index(j - 1, i - 1)] = 1;
						}
					}
					carpets.emplace_back(move(tmp));
				}
			}
		}
	}

	erase_subset(carpets);
	return carpets;
}

void dfs(Bitset current, int num, vector<Bitset> carpets) {
	for(int i = 0; i < carpets.size(); ++i) {
		Bitset tmp(carpets[i] & current);
		for(int j = 0; j < carpets.size(); ++j) {
			if(i == j) continue;
			tmp &= ~carpets[j];
		}

		if(tmp.any()) {
			current &= ~carpets[i];
			++num;
		}
	}

	if(num >= ans) return;
	if(current.none()) {
		ans = num;
		return;
	}

	for(auto &e : carpets) e &= current;
	erase_subset(carpets);

	for(const auto &e : carpets) {
		const Bitset next = current & ~e;
		if(next != current) {
			dfs(move(next), num + 1, carpets);
		}
	}
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	while(cin >> w >> h && w) {
		Bitset scratched;
		vector<vector<int>> p(h + 2, vector<int>(w + 2));

		for(int y = 1; y <= h; ++y) {
			for(int x = 1; x <= w; ++x) {
				cin >> p[y][x];
				if(p[y][x] == 1) scratched.set(index(x - 1, y - 1));
			}
		}

		const vector<Bitset> carpets = init(p);
		ans = h * w;
		dfs(scratched, 0, move(carpets));
		cout << ans << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1236