题目描述

Bob 特别喜欢回文串。

Bob 获得了 $n$ 个字符串，每个字符串的长度都为 $m$，他把这些串排成了一个 $n$ 行 $m$ 列的表格。

由于他特别喜欢回文串，他希望把每一行都变成回文串。每次操作他可以指定一个字符，将它和在它下面的字符交换位置。具体来说，他可以选择下标 $1 \le i < n$ 和 $1 \le j \le m$，然后将第 $i$ 行 $j$ 列的字符和第 $i+1$ 行 $j$ 列的字符交换。

Bob 想知道，最少需要多少次操作，可以把每一行都变成回文串。由于字符串实在是太多了，Bob 只好把求出答案的任务交给你。题目有可能无解，此时只要回答 $-1$ 即可。

输入格式

第一行一个正整数 $T$，表示询问的次数。

接下来 $T$ 次询问，每次询问有若干行。

第一行两个正整数 $n,m$，表示行数和列数。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示 Bob 获得的 $m$ 个字符串。

输出格式

共 $T$ 行，每行一个整数表示该次询问的答案。如果无解答案为 $-1$。

4
3 2
ac
ba
cb
2 2
ab
cd
4 4
babb
abab
abba
bbba
1 1
a

2
-1
3
0

数据范围

• 对于 $30\%$ 的数据，$n = 2$；
• 对于另外 $30\%$ 的数据，每一列每种字符只出现最多一次。 形式化地，对于所有的 $1 \le i \le n$，不存在两个下标 $1 \le j < k \le m$，使得 $s_{i,j} = s_{i,k}$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n,m \le 10^3$，$\sum n \cdot m \le 10^6$，字符集为全体小写英文字母。