太郎君は,近頃弁当作りにはまっている. 太郎君は今日新しい弁当レシピ本を手に入れたので,そこに書いてあるレシピをできるだけ多く試してみたいと思っている.
どのレシピに必要な材料も十分に手元にあるのだが,みんな 2 つ入りの真空パックになっている. 1 つだけ使って 1 つ残したら,残った方はすぐ腐ってしまう. かといって同じレシピの弁当を 2 つ作っても面白くない. だから彼は同じ弁当を複数作らず,しかも半端な材料が残らないようなレシピの組み合わせを選ぶことにした.
レシピ本には,同じ材料を使っても違うレシピの弁当も載っているかもしれないことに注意せよ.
この方針に従うと,今日太郎君は最大で何種類のレシピを試せるのだろうか.
入力は 50 個以下のデータセットからなる. 各データセットは次の形式で表される.
n m b1,1...b1,m ... bn,1...bn,m
1 行目には,レシピ本に書いてあるレシピの数 n と材料の種類数 m が与えられる. n と m は整数であり,1 ≤ n ≤ 500,1 ≤ m ≤ 500,1 ≤ n × m ≤ 500 が成り立つ. 続く n 行には,0 または 1 からなる長さ m の文字列で各レシピの情報が与えられる. bi,j は i 番目のレシピに j 番目の材料が必要かどうかを表し,0 の場合は必要ないこと,1 の場合は必要であることを意味する. 各行は少なくとも 1 つ以上の 1 を含む.
入力の終わりは,2 つのゼロからなる行で表される.
各データセットについて,太郎君が試すことのできるレシピの種類の最大数を 1 行に出力せよ.
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
3 6 0 6