/*

     题意：给出一系列的01字符串，问最少要问几个问题(列)能把它们区分出来

     状态DP+记忆化搜索：dp[s1][s2]表示问题集合为s1。答案对错集合为s2时，还要问几次才能区分出来

             若和答案(自己拟定)相差小于等于1时，证说明已经能区分了，回溯。否则还要加问题再询问

 */

 /************************************************

 * Author        :Running_Time

 * Created Time  :2015-8-13 10:54:26

 * File Name     :UVA_1252.cpp

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef long long ll;

 const int MAXN =  + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 int dp[(<<)+][(<<)+];

 int p[MAXN];

 char str[];

 int m, n;

 int DFS(int s1, int s2) {

     if (dp[s1][s2] != INF)  return dp[s1][s2];

     int cnt = ;

     for (int i=; i<=n; ++i)    {

         if ((p[i] & s1) == s2)  cnt++;

     }

     if (cnt <= )   {

         return dp[s1][s2] = ;

     }

     for (int i=; i<m; ++i) {

         if (s1 & ( << i))  continue;

         int nex = s1 | ( << i);

         dp[s1][s2] = min (dp[s1][s2], max (DFS (nex, s2), DFS (nex, s2 ^ ( << i))) + );

     }

     return dp[s1][s2];

 }

 int main(void)  {       //UVA 1252 Twenty Questions

     while (scanf ("%d%d", &m, &n) == ) {

         if (!m && !n)   break;

         for (int i=; i<=n; ++i)    {

             scanf ("%s", str);  p[i] = ;

             for (int j=; j<m; ++j)  {

                 if (str[j] == '')  {

                     p[i] |= ( << j);

                 }

             }

         }

         memset (dp, INF, sizeof (dp));

         printf ("%d\n", DFS (, ));

     }

     return ;

 }