Making Lunch Boxes

Time limit8sMemory limit512 MB

Summary

Given binary recipe vectors, choose the largest subset with every ingredient appearing in an even number of chosen recipes, meaning their XOR is zero.

Level: Hard8 of 10
Topics: Math, Bit manipulation, Greedy
Solved: No attempts yet

Problem

Taro has been hooked on making lunch boxes lately. He got a new lunch box recipe book today, and he wants to try as many of the recipes in it as he can in one day.

He has plenty of every ingredient, but they all come in vacuum packs of two. If he opens a pack, uses one piece and leaves the other, the leftover goes bad quickly. Making two lunch boxes from the same recipe is no fun. So Taro decided to pick a set of recipes that are all different and leave no ingredient unused. An ingredient is used up pack by pack exactly when the number of chosen recipes that need it is even.

The book may list different recipes that call for the same set of ingredients. Those still count as different recipes.

He may pick no recipe at all, and then the answer is 0. How many recipes can Taro try today at most?

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$ , the number of recipes listed in the book, and $m$ , the number of ingredients. Both $n$ and $m$ are positive integers with $1 \le n \le 500$ , $1 \le m \le 500$ and $1 \le n \times m \le 500$ . Each of the next $n$ lines describes one recipe as a string of length $m$ made of 0 and 1. If $b_{i,j}$ is 1, the $i$ -th recipe needs the $j$ -th ingredient, and if it is 0, it does not. Every such line contains at least one 1.

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

Output

For each dataset, print the maximum number of recipes Taro can try, one per line.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
2 2
10
10
3 2
11
10
01
0 0
```
Expected output
```
2
3
```