Chef has N strings. Each string S_{i} has length M and consists only of lowercase english letters.

Chef likes [palindromes], and would like each S_{i} to be a palindrome. To achieve this, he can perform the following move:
Pick an index i such that 1 ≤ i < N and an index j such that 1 ≤ j ≤ M.
Then, swap the j^{th} character of string S_{i} with the j^{th} character of string S_{i+1}.

Informally, Chef can swap the j^{th} character of any two consecutive strings.

Find the minimum number of moves required to make every string a palindrome. Print -1 if it is not possible to achieve this.

------ Input Format ------

• The first line of input contains a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains two space-separated integers N and M, denoting the number of strings and their length, respectively.
• The i^{th} of the next N lines contains the string S_{i}.

------ Output Format ------

• Print a single integer on a new line as the answer to each test case: the minimum number of swaps needed to make every S_{i} a palindrome, or -1 if this is not possible.

------ Constraints ------

$1 ≤ T ≤ 5\cdot 10^{5}$
$1 ≤ N, M ≤ 5 \cdot 10^{5}$
- Each $S_{i}$ contains only lowercase english letters.
- The sum of $N\times M$ across all test cases won't exceed $5\cdot 10^{5}$.

----- Sample Input 1 ------
4
3 2
ac
ba
cb
2 3
xkx
ptp
4 4
abaa
baba
baab
aabb
4 4
abaa
baba
baab
aaab

----- Sample Output 1 ------
2
0
-1
3

----- explanation 1 ------
Test case $1$: Chef can make all the strings palindromes in two operations:
- First, swap the second characters of $S_{1}$ and $S_{2}$. Now, the strings are $\{\texttt{aa, bc, cb}\}$
- Then, swap the first characters of $S_{2}$ and $S_{3}$. Now, the strings are $\{\texttt{aa, bb, cc} \}$, which are all palindromes.

Test case $2$: Both strings are already palindromes.

Test case $3$: It can be shown that it's impossible to make all $4$ strings simultaneously palindromes.

Test case $4$: One optimal sequence of operations is as follows:
- Swap the first characters of $S_{3}$ and $S_{4}$. Now, the strings are $\{\texttt{abaa, baba, aaab, baab} \}$.
- Swap the second characters of $S_{1}$ and $S_{2}$. Now, the strings are $\{\texttt{aaaa, bbba, aaab, baab} \}$.
- Swap the fourth characters of $S_{2}$ and $S_{3}$. Now, the strings are $\{\texttt{aaaa, bbbb, aaaa, baab} \}$.

Thus, the final strings are all palindromes. It can be proven that we cannot achieve all palindromes in less than $3$ moves.

见题面

见题面