CF1070J Streets and Avenues in Berhattan

Berhattan 是 Berland 的首都。城市中有 $n$ 条东西方向（横向）平行的街道，以及 $m$ 条南北方向（纵向）平行的大道。每条街道与每条大道都相交，形成一个十字路口。因此，Berhattan 一共有 $n \cdot m$ 个十字路口。 最近，Berland 政府进行了更迭。新政府希望以革命英雄的名字来命名所有的街道和大道。 特别委员会准备了 $k$ 个名字的名单。只有这些名字可以被用作街道和大道的新名字。每个名字最多只能使用一次。 委员会成员希望以最小化居民不便为目标来命名街道和大道。他们认为，如果某条街道和某条大道的名字首字母相同，那么它们的交叉口会让居民感到不便。因此，只有每个名字的首字母才是重要的。 给定 $k$ 个名字的首字母，请你求出 $C$ ——在命名完成后，Berhattan 中最小可能的不便十字路口数量。

输入包含一个或多个测试用例。第一行为整数 $t$（$1 \le t \le 30000$），表示测试用例的数量。每个测试用例单独处理，测试用例之间完全独立，互不影响。 每个测试用例的第一行为用空格分隔的三个整数 $n, m, k$（$1 \le n, m \le 30000$；$n + m \le k \le 2 \cdot 10^5$），分别表示街道数、大道数和委员会名单中的名字数。 每个测试用例的第二行为一个长度为 $k$ 的字符串，字符串的第 $i$ 个大写英文字母表示第 $i$ 个名字的首字母。 保证所有测试用例中 $n$ 的总和不超过 $30000$，$m$ 的总和不超过 $30000$，$k$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数 $C$，表示在命名完成后，Berhattan 中最小可能的不便十字路口数量。每个测试用例输出一行。

由 ChatGPT 4.1 翻译