← 返回题目列表

Codeforces · 2132/G

G. 著名编舞家

中文机器翻译题面 查看原题

众所周知,在一场芭蕾舞剧中,有 $$$n \time m$$$ 个芭蕾舞演员,他们的排列可以表示为一个包含 $$$n$$$ 行和 $$$m$$$ 列的表格。每个芭蕾舞演员都会表演 $$$26$$$ 动作之一,这些动作可以用英文字母之一来描述。

编舞瓦迪姆想要消除这个神话。为此,他希望上演一场表演,让所有芭蕾舞演员从起始位置优雅地移动到舞台的另一侧。程序员会发现更容易将这种移动理解为桌子的 $$$180^{\circ}$$$ 旋转。为了维持芭蕾舞剧中视觉叙事的顺序,芭蕾舞演员在不停止动作的情况下瞬间完成这个动作,最终的安排与最初的安排相同。

不幸的是,瓦迪姆明白,以目前的表演和芭蕾舞演员已经计划好的安排,这样的动作是不可能的。因此,他准备邀请更多的芭蕾舞演员来演出。他们可以表演任何动作,占据任何位置,但他们不能站在已经参加芭蕾舞的人之间。最重要的是,最后形成了一张长方形的桌子,可能比原来的还要大。此外,至关重要的是 至少一个 所选字符的 原始排列中的芭蕾舞演员移动到原始排列中其他芭蕾舞演员之一的位置或保持在原来的位置。请告知瓦迪姆他需要邀请的最少数量的芭蕾舞演员。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^5)$$$ - 测试用例的数量。以下几行描述了测试用例。

在每组的第一行中,给出两个整数 $$$n$$$ 和 $$$m$$$ — 表的行数和列数 $$$(1 \le n, m \le 10^6, 1 \le n \cdot m \le 10^6)$$$。

接下来的 $$$n$$$ 行长度 $$$m$$$ 描述了芭蕾舞演员的动作 — 第 $$$i$$$ 行和 $$$j$$$ 列的芭蕾舞演员执行动作 $$$f_{ij}$$$,其中 $$$f_{ij}$$$ — 是一个小写英文字母。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出 Vadim 需要邀请的最少芭蕾舞演员数量。

示例

输入
复制

6
2 3
hey
hey
3 3
abc
def
ghi
3 2
af
fa
te
1 1
x
3 3
uoe
vbe
mbu
2 3
hyh
kop

输出
复制

4
16
2
0
11
3

注意

在第一个示例中,您可以邀请 4 位芭蕾舞演员并按如下方式排列:

heyeh
heyeh

在第二个示例中,您可以邀请 16 位芭蕾舞演员并按如下方式排列:

jkabc
kjdef
ihghi
fedjk
cbakj

在第三个示例中,您可以邀请 2 位芭蕾舞演员并按如下方式安排他们:

et
af
fa
te

此处,受邀芭蕾舞演员以粗体标记。