• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

یک جدول $n \times m$ داریم. در هر خانه از این جدول 0 یا 1 نوشته شده. در هر مرحله می‌توانیم یک سطر را با یک سطر دیگر یا یک ستون را با یک ستون دیگر XOR بگیریم.

بعد از XOR گرفتن سطر ‍$a$ با سطر $b$ داریم: $$a_{j_{new}} = a_{j_{old}} \oplus b_j \quad (1 \le j \le m)$$

بعد از XOR گرفتن ستون ‍$a$ با ستون $b$ داریم: $$a_{i_{new}} = a_{i_{old}} \oplus b_i \quad (1 \le i \le n)$$

و همچنین $$0 \oplus 0 = 0, \quad 0 \oplus 1 = 1, \quad 1 \oplus 0 = 1, \quad 1 \oplus 1 = 0$$

با انجام دادن تعداد دلخواه از عملیات‌های بالا، حداکثر تعداد 1ی که می‌توان در این جدول آورد را محاسبه کنید.

ورودی

در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد سناریوها را نشان می‌دهد. $$1 \leq t \leq 100 , 000$$

در سطر اول هر سناریو، دو عدد صحیح و مثبت $n$ و $m$ که با یک فاصله از هم جدا شده اند و به‌ترتیب تعداد سطرها و ستون‌های جدول را نشان می‌دهد. $$1 \leq n.m \leq 100, 000$$

در $n$ سطر بعدی هر سناریو، در هر کدام یک رشته از $m$ کاراکتر 0 یا 1 می‌آید که وضعیت اولیه جدول را نشان می‌دهد.

تضمین می‌شود که $\sum n.m$ برای همه‌ی سناریوها از $100,000$ بیشتر نمی‌شود.

خروجی

خروجی $t$ سطر دارد و به ازای هر سناریو باید حداکثر تعداد 1هایی که می‌توان با عملیات‌های بالا ساخت را چاپ کنید.

مثال

ورودی نمونه ۱

3
3 4
1010
1010
0000
2 2
01
10
1 5
10101

خروجی نمونه ۱

12
3
5

در مثال اول اگر ابتدا مقدار سطر ۳ را با سطر ۱ XOR بگیریم به جدولی می‌رسیم که ستون‌های آن یکی در میان تماما 1 و تماما 0 است. سپس میتوانیم ستون ۲ و ۴ را با ستون ۱ XOR بگیریم تا به جدولی تماما ‍1 برسیم.

در مثال دوم اگر سطر ۲ را با سطر ۱ XOR بگیریم به جدولی می‌رسیم که تنها خانه ‍0 آن گوشه بالا چپ است و ۳ تا 1 خواهیم داشت. می‌توان نشان داد به جدول تمام ۱ هیچگاه نخواهیم رسید.

در مثال سوم اگر ستون‌های ۲ و ۴ را با ستون ۵ ‍XOR بگیریم به جدولی تماما 1 می‌رسیم.