Binary Grid

You are given a grid $A$ consisting of $N$ rows and $M$ columns, containing only of $0$s and $1$s.

You can do the following operations on $A$:

• Select a row $i$ ($0 \leq i \leq N - 1$) and invert it (i.e. flip every value in that row, such that each $0$ becomes a $1$ and each $1$ becomes a $0$).
• Select a column $j$ ($0 \leq j \leq M - 1$) and invert it.

A binary grid is beautiful if there are no three consecutive equal values in the same row or in the same column. More formally, there is no $i$, $j$ ($0 \leq i \leq N - 1$, $0 \leq j \leq M - 3$) such that $A_{i,j} = A_{i,j} + 1 = A_{i,j} + 2$, and there is no $i$, $j$ ($0 \leq i \leq N - 3, 0 \leq j \leq M - 1$) such that $A_{i,j} = A_{i+1,j} = A_{i+2,j}$.

Task

Your task is to decide whether it is possible to make a given grid beautiful, and if so, then report the minimum number of operations to do it.

Input data

The first line of the input file contains a single integer $T$, the number of testcases. $T$ testcases follow, each preceded by an empty line.

Each testcase consists of:

• a line containing two space-separated integers $N$ and $M$.
• $N$ lines, the $(i+1)$-th of which consisting of string $A_i$ consisting of $0$s and $1$s representing row $i$ of the grid.

Output data

The output file must contain $T$ lines, each consisting of a single integer, the answers of the testcases. If it is possible to make a grid beautiful, then the answer to the testcase is the minimum number of operations to do so, otherwise, if it is impossible, then the answer is $-1$.

Constraints and clarifications

• $1 \leq T \leq 100$
• $1 \leq N \leq 2 \ 000$
• $1 \leq M \leq 2 \ 000$
• $A_{i,j}$ is either $0$ or $1$ for each $0 \leq i \leq N - 1$ and $0 \leq j \leq M - 1$.
• The sum of $N$ over all testcases is at most $2 \ 000$.
• The sum of $M$ over all testcases is at most $2 \ 000$.

Example

stdin

3

4 4
0001
1110
1010
1000

3 3
011
101
110

5 5
11111
10001
11011
10001
11111

stdout

3
0
-1

Explanation

Explanation of the first sample:

In the first testcase, a possible way to make the grid beautiful using $3$ operations is as follows:

• Invert column $0$.
• Invert row $2$.
• Invert column $1$.

In the second testcase, the grid is already beautiful, thus no operations are needed.

In the third testcase, it is impossible to make the grid beautiful using the mentioned operations.