#define  _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}


unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

//li chao tree by ei1333. It's public available.
// https://ei1333.github.io/luzhiled/snippets/structure/li-chao-tree.html
/*
template< typename T >
struct LiChaoTree {
    struct Line {
        T a, b;

        Line(T a, T b) : a(a), b(b) {}

        inline T get(T x) const { return a * x + b; }

        inline bool over(const Line& b, const T& x) const {
            return get(x) < b.get(x);
        }
    };

    vector< T > xs;
    vector< Line > seg;
    int sz;

    LiChaoTree(const vector< T >& x, T INF) : xs(x) {
        sz = 1;
        while (sz < xs.size()) sz <<= 1;
        while (xs.size() < sz) xs.push_back(xs.back() + 1);
        seg.assign(2 * sz - 1, Line(0, INF));
    }

    void update(Line& x, int k, int l, int r) {
        int mid = (l + r) >> 1;
        auto latte = x.over(seg[k], xs[l]), malta = x.over(seg[k], xs[mid]);
        if (malta) swap(seg[k], x);
        if (l + 1 >= r) return;
        else if (latte != malta) update(x, 2 * k + 1, l, mid);
        else update(x, 2 * k + 2, mid, r);
    }

    void update(T a, T b) { // ax+b
        Line l(a, b);
        update(l, 0, 0, sz);
    }

    T query(int k) { // xs[k]
        const T x = xs[k];
        k += sz - 1;
        T ret = seg[k].get(x);
        while (k > 0) {
            k = (k - 1) >> 1;
            ret = min(ret, seg[k].get(x));
        }
        return ret;
    }
};

#define int long long
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> landmarks;
    vector<vector<int>> costs;
    REP(i, n) {
        vector<int> tmp;
        REP(q, m) {
            int b;
            cin >> b;
            b = xor128() % 10000000;
            tmp.push_back(b);
        }
        landmarks.push_back(tmp);
    }
    REP(i, n) {

        vector<int> tmp;
        {
            REP(q, m) {
                int b;
                cin >> b;
                b = xor128() % 100000000;
                tmp.push_back(b);
            }
        }
        costs.push_back(tmp);
    }
    vector<LiChaoTree<int>> yoko; // size should be m
    REP(i, n) {
        vector<int> hoge(m);
        REP(q, m) {
            hoge[q] = q;
        }
        LiChaoTree<int> now(hoge, 1e18);//size should be n
        yoko.push_back(now);
    }
    vector<vector<int>> dp = landmarks;
    for (int q = 0; q < m; ++q) {
        vector<int> hoge(n);
        REP(i, n) {
            hoge[i] = i;
        }
        LiChaoTree<int> now(hoge, 1e18);//size should be n

        for (int i = 0; i < n; ++i) {
            int now_min = costs[0][0] * (i + q);
            if (q < 0) {
                int geko = yoko[i].query(q);
                now_min = min(now_min, geko);
            }
            if (i != 0) {
                int geko = now.query(i);
                now_min = min(now_min, geko);
            }
            dp[i][q] = now_min;
            yoko[i].update(costs[i][q], landmarks[i][q] + dp[i][q] - q * costs[i][q]);
            now.update(costs[i][q], landmarks[i][q] + dp[i][q] - i * costs[i][q]);
        }
    }

    cout << dp[n - 1][m - 1] << endl;
}
*/

#define int ll
int dp[177147];
int bit[100];
int n, m;
vector<int> inputs;
int dfs(int now) {
    if (dp[now] != -1) return dp[now];
    int diff = 0;
    int comp = 0;
    int hoge = now;
    for (int q = 0; q < n; ++q) {
        if (hoge % 3 != 2) {
            comp += (1 << q);
            diff += (1 << q) * (hoge % 3);
        }
        hoge /= 3;
    }
    int cnt = 0;
    REP(i, inputs.size()) {
        if ((inputs[i] & comp) == diff) {
            cnt++;
        }
    }
    if (cnt == 1) return dp[now] = 0;
    else if(cnt == 0) return dp[now] = -1e9;
    int ans = 100;
    hoge = now;
    for (int q = 0; q < n; ++q) {
        if (hoge % 3 == 2) {
            int tmp = now - bit[q] * 2;
            int tea = max(dfs(tmp), dfs(tmp + bit[q]));
            if (tea == -1e9) continue;
            ans = min(ans,tea + 1);
        }
        hoge /= 3;
    }
    return dp[now] = ans;
}

void solve(){
    bit[0] = 1;
    for (int q = 1; q < 13; ++q) {
        bit[q] = bit[q - 1] * 3;
    }
    while (true) {
        cin >> n >> m;
        if (n == 0) return;
        REP(i, 177147) {
            dp[i] = -1;
        }
        inputs.clear();
        REP(i, m) {
            string s;
            cin >> s;
            int a = 0;
            REP(q, s.length()) {
                if (s[q] == '1') {
                    a += (1 << q);
                }
            }
            inputs.push_back(a);
        }
        cout << dfs(bit[n] - 1) << endl;
    }
}
#undef int
int main() {
    init();
    solve();
}


Measured memory_bytes: 4564