스무고개

방 안에 물건이 $n$개 있고, 각 물건은 여러 개의 특징으로 설명된다. 하나의 특징은 "예" 또는 "아니오"로만 답할 수 있는 질문에 해당한다.

특징의 종류는 모두 $m$개이며, 이 $m$개의 특징만으로 방 안의 모든 물건을 구별할 수 있다. 즉, 각 물건은 길이가 $m$인 이진(불리언) 수열로 표현되고, 서로 다른 두 물건은 적어도 하나의 특징에서 값이 다르다.

당신은 방 안의 어떤 물건 하나가 무엇인지 알아내려고 한다. 그래서 그 물건의 특징을 모두 알고 있는 사람에게 질문을 한다. 질문은 언제나 "이 물건은 $j$번째 특징을 가지고 있습니까?"라는 형태이고, 대답은 "예" 또는 "아니오"이다. 당신은 이전 답을 들은 뒤에 다음 질문을 정할 수 있다.

질문을 한 번 할 때마다 100원을 내야 하므로, 당신은 질문 횟수(즉 내야 하는 돈)를 최대한 줄이려고 한다. 당신은 방 안에 있는 모든 물건의 특징을 알고 있지만, 알아내려는 물건이 그중 어떤 것인지는 모른다. 따라서 질문을 시작하기 전에 미리 전략(질문의 순서와, 답에 따라 어떻게 나눌지)을 세울 수 있다.

가장 좋은 전략을 사용한다고 할 때, 어떤 물건이든 반드시 구별해 내기 위해 최악의 경우에 필요한 질문 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 특징의 개수 $m$과 물건의 개수 $n$이 주어진다 ($0 < m \le 11$, $0 < n \le 128$). 이어지는 $n$개의 줄에는 각 물건의 특징이 주어진다. 각 물건의 특징은 길이가 $m$인 이진 문자열로, 각 자리의 값은 1(예) 또는 0(아니오)이다. 서로 다른 두 물건의 특징이 완전히 같은 경우는 없다.

각 테스트 케이스마다, 가장 좋은 전략을 사용했을 때 어떤 물건이든 구별하기 위해 최악의 경우에 필요한 질문 횟수의 최솟값을 한 줄에 출력한다.