import std.stdio, std.string, std.algorithm;

int n, m;
string xs[];
int memo[];

void main(){
	for(;scanf("%d%d\n", &m, &n) && n;){
		xs.length = n;
		foreach(ref x; xs) x = readln.chomp;
		memo.length = 3^^m;
		memo[] = -1;
		writeln(solve(0));
	}
}

int solve(ulong state){
	if(memo[state] >= 0) return memo[state];
	int ans = int.max;
	scope(exit) memo[state] = ans;
	auto n = xs.length, m = xs[0].length;
	auto cands = count!(
		(string x){
			foreach(i; 0..m){
				if(state/(3^^i)%3 &&
					((state/(3^^i)%3 == 1) ^ (x[i] == '1'))) return false;
			}
			return true;
		}
	)(xs);
	if(cands <= 1) return ans = 0;
	foreach(i; 0..m)if(state/(3^^i)%3 == 0)
		ans = min(ans, 1 + max(solve(state+(3^^i)*1), solve(state+(3^^i)*2)));
	return ans;
}