/*
  AOJ 1302
  Title:
  @kankichi573
*/
#include <stdio.h>
#include <limits.h>
#include <string.h>
#define min(x,y) ((x<y)?(x):(y))
#define max(x,y) ((x>y)?(x):(y))

int m,n;
int data[128];
int memo1[2048][11];
int memo2[2048][11];


int log2ceil(int n)
{
  int i;
  if(n==0)
    return(-1);
  for(i=8;i>=0;i--)
    if(n > (1<<i))
      return(i+1);
  return(0); // never reach if n > 0 && n <= 128
}
int conv_bin(char buf[],int len)
{
  int i,ret;

  ret=0;
  for(i=0;i<len;i++)
    if(buf[i] & 1)
      ret+=(1<<(len-1-i));
  return(ret);
}

solve(int maskbit,int mask,int nn,int lv)
{
  int i,j,m1,c1,c2,ret1,ret2,ret,min_;
  int log2ceil_n;
  int bit;
  
  if(nn==1)
    {
      //printf("*");
      return(0);
    }
  //  if(maskbit==((1<<n)-1))
  //  return(1);
  min_=INT_MAX;ret1=ret2=0;
  log2ceil_n=log2ceil(nn);
  for(i=0;i<m;i++)
    {
      m1=1<<i;
      if(m1 & maskbit)
	continue;
      //printf("m1mskb=%d %d lv=%d n=%d\n",m1,maskbit,lv,nn);
      c1=c2=0; // bit i assert no kazu
     
      bit=1+log2ceil(maskbit ^ mask);
      printf("%d %d %d\n",maskbit,mask,bit);
      /*
      if(memo1[maskbit][bit])
	{
	  c1=memo1[maskbit][bit];
	  c2=memo2[maskbit][bit];
	goto HIT;
	}
      */
      for(j=0;j<n;j++)
	if(maskbit==0 || (data[j]&maskbit)==mask)
	  {
	    c2++;
	    if(data[j] & m1)
	      c1++;
	  }
	  memo1[maskbit][bit]=c1;
	  memo2[maskbit][bit]=c2;
    HIT:
      printf("c1c2=%d %d\n",c1,c2);
      if(c1>0 && c1 < c2)
	{
	  ret1=solve((maskbit|m1),mask|m1,c1   ,lv+1);
	  ret2=solve((maskbit|m1),mask   ,c2-c1,lv+1);
	  //printf("r1r2=%d %d\n",ret1,ret2);
	  ret=max(ret1,ret2)+1;
	}
      if(ret==log2ceil_n)
	{
	  min_=ret;
	  //printf("opted\n");
	  goto END;
	}
	min_=min(min_,ret);
    }
    
 END:
  return(min_);
}
main()
{
  int i,ret;
  char buf[13];

  while(scanf("%d %d",&m,&n) && (m||n))
    {
      memset(&memo1[0][0],0,sizeof(int)*2048*11);
      memset(&memo2[0][0],0,sizeof(int)*2048*11);
      //printf("mn=%d %d\n",m,n);
      for(i=0;i<n;i++)
	{
	  scanf("%s",&buf[0]);
	  data[i]=conv_bin(buf,m);
	}
      
      ret=solve(0,0,n,1);
      printf("%d\n",ret);
    }
  
  return(0);

}