众所周知,在一场芭蕾舞剧中,有 $$$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 需要邀请的最少芭蕾舞演员数量。
示例
输入复制
62 3heyhey3 3abcdefghi3 2affate1 1x3 3uoevbembu2 3hyhkop
输出复制
4 16 2 0 11 3
注意
在第一个示例中,您可以邀请 4 位芭蕾舞演员并按如下方式排列:
| h | e | y | e | h |
| h | e | y | e | h |
在第二个示例中,您可以邀请 16 位芭蕾舞演员并按如下方式排列:
| j | k | a | b | c |
| k | j | d | e | f |
| i | h | g | h | i |
| f | e | d | j | k |
| c | b | a | k | j |
在第三个示例中,您可以邀请 2 位芭蕾舞演员并按如下方式安排他们:
| e | t |
| a | f |
| f | a |
| t | e |
此处,受邀芭蕾舞演员以粗体标记。