#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
struct aa {
	vector<vector<int>>field;
	int sx;
	int sy;
	int time;
};
class Compare {
public:
	//aa?????????????????¶
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};
map<vector<vector<int>>, int>mp;
int main() {
	while (1) {
		int X, Y; cin >> X >> Y;
		if (!X)break;
		priority_queue<aa, vector<aa>, Compare>que;
		{
			int sx=-1, sy=-1;
			vector<vector<int>>sfield(Y + 2, vector<int>(X + 2));
			bool flag = true;
			for (int i = 0; i < Y; ++i) {
				for (int j = 0; j < X; ++j) {
					cin >> sfield[i + 1][j + 1];
					if (flag&&sfield[i + 1][j + 1]) {
						sx = j + 1;
						sy = i + 1;
						flag = false;
					}
				}
			}
			que.push(aa{ sfield, sx, sy, 0 });
			mp[sfield] = 0;
		}
		int ans = -1;
		while (que.size()) {
			aa atop(que.top());
			que.pop();
			if (atop.sx == -1) {
				ans = atop.time;
				break;
			}
			for (int nsy = atop.sy; atop.field[nsy][atop.sx];--nsy)
			{
				int nsx = atop.sx;
				while (atop.field[nsy][nsx]) {
					int nsize = atop.sx - nsx + 1;
					while (1) {
						bool ok = true;
						for (int ay = nsy; ay < nsy + nsize; ++ay) {
							for (int ax = nsx; ax < nsx + nsize; ++ax) {
								if (!atop.field[ay][ax]) {
									ok = false;
									break;
								}
							}
							if (!ok)break;
						}
						if (!ok) {
							nsize--;
							break;
						}
						nsize++;
					}
					if (nsize == atop.sx - nsx)break;
					else {
						vector<vector<int>>nfield(atop.field);
						for (int ay = nsy; ay < nsy + nsize; ++ay) {
							for (int ax = nsx; ax < nsx + nsize; ++ax) {
								if (nfield[ay][ax] == 0)assert(false);
								nfield[ay][ax] = 2;
							}
						}
						if (!mp.count(nfield)) {
							int asx = -1, asy = -1;
							bool flag = true;
							for (int i = 0; i < Y + 2; ++i) {
								for (int j = 0; j < X + 2; ++j) {
									if (flag&&nfield[i][j] == 1) {
										asx = j; asy = i;
										flag = false;
									}
								}
							}
							mp[nfield] = atop.time + 1;
							que.push(aa{ nfield,asx,asy,atop.time + 1 });
						}
					}
					nsx--;
				}
			}

			//{
			//	const int nsx = atop.sx;
			//	int nsy = atop.sy;
			//	while (atop.field[nsy][nsx]) {
			//		int nsize = atop.sy - nsy + 1;
			//		while (1) {
			//			bool ok = true;
			//			for (int ay = nsy; ay < nsy + nsize; ++ay) {
			//				for (int ax = nsx; ax < nsx + nsize; ++ax) {
			//					if (!atop.field[ay][ax]) {
			//						ok = false;
			//						break;
			//					}
			//				}
			//				if (!ok)break;
			//			}
			//			if (!ok) {
			//				nsize--;
			//				break;
			//			}
			//			nsize++;
			//		}
			//		if (nsize == atop.sy - nsy)break;
			//		else {
			//			vector<vector<int>>nfield(atop.field);
			//			for (int ay = nsy; ay < nsy + nsize; ++ay) {
			//				for (int ax = nsx; ax < nsx + nsize; ++ax) {
			//					if (nfield[ay][ax] == 0)assert(false);
			//					nfield[ay][ax] = 2;
			//				}
			//			}
			//			if (!mp.count(nfield)) {
			//				int asx = -1, asy = -1;
			//				bool flag = true;
			//				for (int i = 0; i < Y + 2; ++i) {
			//					for (int j = 0; j < X + 2; ++j) {
			//						if (flag&&nfield[i][j] == 1) {
			//							asx = j; asy = i;
			//							flag = false;
			//						}
			//					}
			//				}
			//				mp[nfield] = atop.time + 1;
			//				que.push(aa{ nfield,asx,asy,atop.time + 1 });
			//			}
			//		}
			//		nsy--;
			//	}
			//}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 10360