贝尔哈坦是贝尔兰的首府。东西方向(水平)有$$$n$$$条街道平行,南北方向(垂直)平行有$$$m$$$条大道。每条街道与每条大道相交,形成十字路口。因此 Berhattan 总共有 $$$n \cdot m$$$ 十字路口。
最近,伯兰政府发生了变化。新政府希望以革命英雄的名字命名所有大道和街道。
特别委员会准备了$$$k$$$名单。只有这些名称才能用作街道和大道的新名称。每个名称最多可以使用一次。
委员会成员希望以尽量减少给居民带来不便的方式命名街道和大道。他们认为,如果街道和大道的名称以相同的字母开头,那么他们的十字路口就会不方便。因此,只有每个名字的第一个字母很重要。
给定 $$$k$$$ 名称的首字母,找到 $$$C$$$ — 命名过程后 Berhattan 中不方便十字路口的最小可能数量。
输入
输入包含一个或多个要处理的测试用例。第一行包含 $$$t$$$ ($$$1 \le t \le 30000$$$) — 测试用例的数量。单独解决测试用例,测试用例完全独立,互不影响。
$$$t$$$ 测试用例的描述如下。每个测试用例都以空格分隔的数字 $$$n, m, k$$$ 开头 ($$$1 \le n,m \le 30000$$$; $$$n+m \le k \le 2\cdot10^5$$$) — 分别是街道数量、大道数量和委员会列表中的名称数量。
每个测试用例的第二行包含一串$$$k$$$大写英文字母。字符串的第 $$$i$$$ 字母是委员会列表中第 $$$i$$$ 名称的第一个字母。
保证所有测试用例的数字 $$$n$$$ 之和不大于 $$$30000$$$。同样,所有测试用例的数字总和 $$$m$$$ 不大于 $$$30000$$$。所有测试用例的数字 $$$k$$$ 之和不大于 $$$2\cdot10^5$$$。
输出
对于每个测试用例,在单独的行中打印单个数字 $$$C$$$ — 命名过程后 Berhattan 中不方便的十字路口的尽可能少的数量。
示例
输入 #1
2 2 3 9 EEZZEEZZZ 2 7 9 EEZZEEZZZ
输出 #1
0 4
输入 #2
2 4 4 8 CZBBCZBC 1 1 4 TTCT
输出 #2
1 0