#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reg(i,a,b) for(int i=(a);i<=(b);i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=(b);i>=(a);i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX

int n,m;
char s[200][200];


int dp[200000];

int pow(int p,int q){
  int res=1;
  rep(i,q)res*=p;
  return res;
}

int main(void){

  for(;;){
    scanf("%d%d",&n,&m);
    if(n==0)break;
    rep(i,m)scanf("%s",s[i]);
    memset(dp,0,sizeof(dp));

    int nl=pow(3,n);
    int ans=100;

    //printf("nl .. %d\n",nl);
    
    rep(i,nl){
      int nb[15]={},ii=i;
      rep(j,n){
	nb[j]=ii%3;
	ii/=3;
      }

      /*
      rep(j,n){
	printf("%d ",nb[j]);
      }
      printf("\n");*/

      int ns=0;
      rep(j,m){
	bool ok=true;
	rep(k,n){
	  if(nb[k]!=2 && (((char)nb[k])+'0')!=s[j][k])ok=false;
	}
	if(ok)ns++;
      }
      if(ns<=1){
	if(ns==1)dp[i]=0;
	else dp[i]=1000;
	//printf("%d\n",i);
	continue;
      }

      
      int nmin=100;
      int tb[15]={};
      rep(j,n){
	tb[j]=nb[j];
	//printf("%d ",tb[j]);
      }
      //printf(" ..tb\n");
      
      rep(j,n){
	if(tb[j]!=2)continue;
	
	int ne=-100;
	rep(p,2){
	  tb[j]=p;

	  int t=0,bas=1;
	  rep(k,n){
	    t+=tb[k]*bas;
	    bas*=3;
	  }
	  //if(i==8)printf("tot .. %d\n",t);
	  ne=max(ne,dp[t]);
	  
	  tb[j]=nb[j];
	}
	nmin = min(ne,nmin);
	//printf("doing %d %d %d\n", i,j,ne);
      }
      
      dp[i]=nmin+1;

      //printf("do .. %d %d %d \n",i,ns,dp[i]);
      
      
    }
    printf("%d\n",dp[pow(3,n)-1]);
  }
  return 0;
}