ICPC2017D.java

import java.util.*;

public class Main {
    Scanner sc = new Scanner(System.in);

    int n, m;

    String xor(String a, String b) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; ++i) {
            if (a.charAt(i) == b.charAt(i)) {
                sb.append(0);
            } else {
                sb.append(1);
            }
        }
        return sb.toString();
    }

    void run() {
        for (; ; ) {
            n = ni();
            m = ni();
            if (n == 0) {
                break;
            }
            String[] b = new String[n];
            for (int i = 0; i < n; ++i) {
                b[i] = sc.next();
            }
            String zero = xor(b[0], b[0]);
            String xor = zero;
            for (int i = 0; i < n; ++i) {
                xor = xor(xor, b[i]);
            }
            HashMap<String, Integer> map = new HashMap<>();
            map.put(xor, 0);
            Queue<String> queue = new LinkedList<>();
            queue.add(xor);
            while (queue.size() > 0) {
                String node = queue.poll();
//                debug(node, map.get(node));
                if (node.equals(zero)) {
                    break;
                }
                for (int i = 0; i < n; ++i) {
                    String next = xor(node, b[i]);
                    if (map.containsKey(next)) {
                        continue;
                    }
                    map.put(next, map.get(node) + 1);
                    queue.add(next);
                }
            }
            if (map.containsKey(zero)) {
                System.out.println(n - map.get(zero));
            } else {
                System.out.println(0);
            }
        }
    }

    int ni() {
        return sc.nextInt();
    }

    public static void main(String[] args) {
        new Main().run();
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }
}