很久很久以前，王国里有 $n$ 个城市和 $m$ 条铁路。每条铁路包含许多城市，且每个城市恰好位于一条铁路上。由于有些城市之间没有铁路连接，人们在城市间往返时常常需要经历艰苦的旅程。交通不便严重阻碍了王国经济的发展，因此国王很快决定开通几条航线。

根据国王的指令，城市被划分为 $k$ 个区域，这样人们就可以乘坐热气球在属于同一个区域的任意两个城市之间往返。此外，在计划前往其他任何城市时，王国里的人们可以选择结合使用火车和热气球，而无需其他交通工具，这也是经济持续繁荣的原因。

国王想知道他制定的政策是否惠及了所有人。然而，在他去世前并没有得出结论，因为这需要大量的计算。现在计算能力提高了，这个问题被重新提出来解决。假设乘坐热气球直接从一个城市移动到另一个城市需要花费一小时，而乘坐火车从一个城市移动到铁路上相邻的城市也需要花费一小时，请你计算从一个城市移动到另一个城市所需的平均时间成本，并报告 $\frac{n(n-1)}{2}$ 与该平均值的乘积，结果应当是一个整数。

为了避免输入数据过大，每个城市用前 $k$ 个小写字母中的一个表示，代表铁路上的一个站点，且用相同字母表示的城市属于同一个区域。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。接下来描述所有测试用例。对于每个测试用例：

第一行包含三个整数 $n$、$m$ 和 $k$。

接下来的 $m$ 行，每行包含一个非空字符串，由前 $k$ 个小写字母组成，按顺序描述了一条铁路上的站点。

• $1 \le T \le 1000$
• $1 \le m \le n \le 10^6$
• $1 \le k \le 16$
• 每个区域至少包含一个城市。
• 所有测试用例中 $n$ 的总和不超过 $5 \times 10^6$。
• 至多有 5 个测试用例满足 $k > 8$。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是从 1 开始的测试用例编号，$y$ 是该测试用例的答案（以小时为单位）。

样例

输入 1

3
2 1 2
ab
2 2 1
a
a
5 2 3
abb
ac

输出 1

Case #1: 1
Case #2: 1
Case #3: 20