C. Binary Flip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given $$$n$$$ binary strings each of length $$$m$$$. In each operation, You can choose a prefix of an string and flip it (change each $$$0$$$ to $$$1$$$ and vice versa).

Now the goal is to make all these $$$n$$$ strings equal to each other. You should print the minimum number of operations needed to achieve the goal.

Input

In the first line of input you'll be given a number $$$t$$$ which shows the number of testcases : $$$$$$1 \le t \le 10^3$$$$$$.

In the second line of input you'll receive two integers $$$n$$$ and $$$m$$$ which shows the number of strings and their length.

$$$$$$1 \le n, m \le 10^5$$$$$$.

In the next $$$n$$$ lines you'll receive strings of length $$$m$$$ which consist only of $$$0$$$ and $$$1$$$.

It is guaranteed that sum of $$$n \cdot m$$$ overall testcases does not exceed $$$10^5$$$.

Output

In each line print the minimum number of operations needed to make the strings of each test equal to each other.

Example
Input
3
1 1
0
2 2
01
10
4 5
01010
00101
11000
00110
Output
0
1
5
Note

Explanation for testcase $$$2$$$ :

  • You only should choose prefix of length $$$2$$$ for the first string and then it will become $$$01 \rightarrow 10$$$