Problem: Making Lunch Boxes

Taro has been hooked on making lunch boxes recently. Taro has obtained a new lunch box recipe book today, and wants to try as many of the recipes listed in the book as possible.

Enough of the ingredients for all the recipes are at hand, but they all are in vacuum packs of two. If only one of them is used leaving the other, the leftover will be rotten easily, but making two of the same recipe is not interesting. Thus he decided to make a set of lunch boxes, each with different recipe, that wouldn't leave any unused ingredients.

Note that the book may include recipes for different lunch boxes made of the same set of ingredients.

How many lunch box recipes can Taro try today at most following his dogma?

Input

The input consists of at most 50 datasets, each in the following format.


n m
b1,1...b1,m
...
bn,1...bn,m


The first line contains n, which is the number of recipes listed in the book, and m, which is the number of ingredients. Both n and m are positive integers and satisfy 1 ≤ n ≤ 500, 1 ≤ m ≤ 500 and 1 ≤ n × m ≤ 500. The following n lines contain the information for each recipe with the string of length m consisting of 0 or 1. bi,j implies whether the i-th recipe needs the j-th ingredient. 1 means the ingredient is needed for the recipe and 0 means not. Each line contains at least one 1.

The end of the input is indicated by a line containing two zeros.

Output

For each dataset, output the maximum number of recipes Taro can try.

Sample Input


4 3
110
101
011
110
7 1
1
1
1
1
1
1
1
4 5
10000
01000
00100
00010
6 6
111111
011000
100000
000010
100001
100100
0 0


Output for the Sample Input


3
6
0
6






Example

Input

4 3
110
101
011
110
7 1
1
1
1
1
1
1
1
4 5
10000
01000
00100
00010
6 6
111111
011000
100000
000010
100001
100100
0 0


Output

3
6
0
6

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define _dec(i,N,j) for(int i = (N-1);i >= (j);i--)
#define _rec(i,N,j) for(int i = (N);i >=(j);i--)
#define ALL(x) x.begin(),x.end()
#define MEM(a,n) memset(a,n,sizeof(a))
#define fst first
#define scd second
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

int get_int(){int x;scanf("%d",&x);return x;}
LL get_ll(){LL x;scanf("%lld",&x);return x;}
double get_db(){double x;scanf("%lf",&x);return x;}

template<typename T> int chmin(T &a,T b){if(a > b){a = b;return 1;}else return 0;}
template<typename T> int chmax(T &a,T b){if(a < b){a = b;return 1;}else return 0;}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {_for(i,0,v.size()) os << v[i] << " ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){for(auto a:v) os << a <<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){os << v.fst <<" "<<v.scd << " ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>& v){for(auto a:v) cout << a << endl;return os;}

static const int dx[8] = { 1,  0, -1,  0,  1, -1,  1, -1};
static const int dy[8] = { 0,  1,  0, -1,  1, -1, -1,  1};
const double pi  = acos(-1.0);
const double eps = 1e-8;
const LL  INF  = 0x3f3f3f3f3f3f3f3f;
const int inf  = 0x3f3f3f3f;
const int mod = 1e9+7;

int n,m;
const int maxn = 505;
const int maxs = 1<<23;
string recip[maxn];
LL recipint[maxn];

int dp[2][maxs];


bool get_input(){
    scanf("%d %d",&n,&m);
    if(!n && !m) return false;
    _for(i,0,n){
        cin >> recip[i];
    }
    return true;
}

LL to_int(string &s){
    LL ret = 0;
    int sz = s.size();
    _for(i,0,sz){
        if(s[i] == '1'){
            ret = ((1LL)<< (sz-i-1)) | ret;
        }
    }
    return ret;
}

void xxor(string &a,string &b){
    int sz = a.size();
    _for(i,0,sz){
        if(a[i] == b[i]) a[i] = '0';
        else a[i] = '1';
    }
}

bool check(string &kk){
    int sz = kk.size();
    _for(i,0,sz){
        if(kk[i] == '1') return false;
    }
    return true;
}

int searching(){
    int full = 1 << n;
    int ret = 0;

    string stat;
    _for(i,0,m){
        stat.push_back('0');
    }

    if(m > 63){
        for(int i = 0; i < full;i++){
            int num = 0;
            string kk = stat;

            _for(k,0,n){
                if((1 << k) & i){
                    xxor(kk,recip[k]);
                    num++;
                }
            }

            if(check(kk)) chmax(ret,num);
        }
    }
    else{
        _for(i,0,n){
            recipint[i] = to_int(recip[i]);
        }
        for(int i = 0; i < full;i++){
            int num = 0;
            LL kk = 0;

            _for(k,0,n){
                if((1 << k) & i){
                    kk ^= recipint[k];
                    num++;
                }
            }

            if(!kk) chmax(ret,num);
        }
    }


    return ret;
}



int dpsolve(){
    int t = 0;
    memset(dp,-1,sizeof(dp));
    _for(i,0,n){
        recipint[i] = to_int(recip[i]);
    }

    int maxss = (1<<m);

    dp[0][0] = 0;
    _for(i,0,n){
        int stat = recipint[i];

        _for(j,0,maxss){
            if(dp[t][j] != -1){
                chmax(dp[t^1][j],dp[t][j]);
                chmax(dp[t^1][j ^ stat],dp[t][j] + 1);
            }
        }
        t = 1^t;
    }

    return dp[t][0];
}

int main()
{
    while(get_input()){
        if(n <= 21){
            cout << searching() << endl;;
        }
        else{
            cout << dpsolve() << endl;
        }

    }
    return 0;
}