• 来源：37th Petrozavodsk Programming Camp, Summer 2019, Day 8: Jingzhe Tang Contest 2, XIX Open Cup Onsite, Problem I. Routes
• 时间限制：4 seconds
• 空间限制：512 mebibytes

题目描述

很久以前，有一个王国拥有 $n$ 座城市和 $m$ 条铁路。每条铁路按顺序经过若干座城市，而每座城市恰好位于一条铁路上。铁路只能连接同一条线路上相邻的城市，因此从一座城市去另一座城市常常需要绕很远的路。

为了改善交通，国王把所有城市划分为 $k$ 个行政区。同一个行政区内任意两座城市之间，都可以直接乘坐热气球往返。之后，人们出行时只能使用两种交通方式：

• 沿铁路从一座城市到同一铁路上的相邻城市；
• 乘热气球从一座城市到同一区内的另一座城市。

每次沿铁路移动到相邻城市需要 $1$ 小时；每次乘热气球从一座城市直接到同一区内另一座城市也需要 $1$ 小时。

国王想知道这项政策给全国带来了多大改善。请你计算任意两座不同城市之间，使用上述交通方式所需最短时间的平均值，并输出这个平均值乘以

后的结果。题目保证该结果是整数。换句话说，你需要输出所有无序城市对之间最短时间的总和。

为了避免输入过大，每座城市用前 $k$ 个小写字母之一表示。同一个字母表示这些城市属于同一个行政区。每一行字符串表示一条铁路，字符串中的字符依次表示这条铁路沿线城市所属的行政区。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

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

接下来 $m$ 行，每行包含一个非空字符串，由前 $k$ 个小写字母组成，按顺序描述一条铁路上的城市。所有字符串的总长度为 $n$。

输出格式

对于第 $x$ 组测试数据，输出一行：

Case #x: y

其中 $x$ 从 $1$ 开始编号，$y$ 为该组测试数据的答案，单位为小时。

数据范围

• $1\le T\le 1000$；
• $1\le m\le n\le 10^6$；
• $1\le k\le 16$；
• 每个行政区至少包含一座城市；
• 所有测试数据中 $n$ 的总和不超过 $5\cdot 10^6$；
• 至多有 $5$ 组测试数据满足 $k>8$。

样例 1

输入

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

输出

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