### constant

INF = 1 << 30

### subroutines

def count_rec(bits, mask)
  return $cache[bits][mask] if $cache[bits][mask]

  c = 0
  for obj in $objs
    c += 1 if (obj & mask) == bits
  end
  return ($cache[bits][mask] = 0) if c <= 1

  minc = INF

  for i in (0...$m)
    b = 1 << i
    mask0 = mask | b
    if mask != mask0
      c0 = count_rec(bits, mask0) + 1
      c1 = count_rec(bits | b, mask0) + 1
      c = (c0 > c1) ? c0 : c1
      minc = c if minc > c
    end
  end

  $cache[bits][mask] = minc
end

### main

loop do
  $m, $n = gets.split.map(&:to_i)
  break if ($m | $n) == 0

  $objs = $n.times.map{gets.strip.to_i(2)}
  #p $objs.map{|o| o.to_s(2)}

  $cache = (1 << $m).times.map{{}}

  minc = count_rec(0, 0)
  puts minc
end