def f(x)
    return 0 if x & (x - 1) == 0
    return $memo[x] if $memo[x]
    cand = []
    (0..$m-1).each do |i|
        yes = x & $question[i]
        no = x - yes
        next if yes == 0 || no == 0
        k = f(yes) + 1 
        l = f(no) + 1
        cand << (k > l ? k : l)
    end 
    $memo[x] = cand.min
end 

loop do
    $m, n = gets.split.map(&:to_i)
    break if $m == 0
    rows = (1..n).map { gets.to_i(2) }
    if n == 1
        puts 0
        next 
    end 
    
    $question = (0..$m-1).map do |i|
        x = 0 
        (0..n-1).each do |j|
            x += (1 << j) if rows[j][i] == 1
        end 
        x
    end 
    
    $memo = {}
    p f(2**n-1)
end