경로

먼 옛날 한 왕국에는 $n$개의 도시와 $m$개의 철도가 있었다. 각 철도에는 여러 도시가 놓여 있었고, 각 도시는 정확히 하나의 철도 위에 있었다. 철도로 연결되지 않은 도시도 있어서, 사람들은 도시 사이를 오갈 때 자주 힘든 여정을 감수해야 했다. 이런 불편한 교통은 왕국의 경제 발전을 가로막았고, 왕은 몇 개의 항공 노선을 열기로 했다.

왕의 명령에 따라 도시들은 $k$개의 구역으로 나뉘었다. 같은 구역에 속한 두 도시 사이는 열기구로 이동할 수 있다. 또한 어느 도시에서든 기차와 열기구만 이용해 다른 모든 도시로 갈 수 있다.

왕은 자신의 정책이 모든 사람에게 이익이 되었는지 알고 싶어 했지만, 계산량이 너무 많아 답을 알아내기 전에 세상을 떠났다. 이제 컴퓨터 성능이 좋아졌으므로 이 문제를 다시 푼다.

한 도시에서 다른 도시로 열기구를 타고 직접 가는 데 1시간이 걸린다. 한 도시에서 철도로 인접한 도시로 가는 데도 1시간이 걸린다. 이 두 가지 교통수단만 사용해서 두 도시 사이를 이동하는 평균 시간을 구하라. 그리고 $\frac{n(n-1)}{2}$과 그 평균의 곱을 출력하라. 이 값은 정수여야 한다.

입력을 작게 하기 위해 각 도시는 처음 $k$개의 소문자 중 하나로 표현한다. 그 글자가 도시가 속한 구역이므로, 같은 글자를 가진 도시는 같은 구역에 속한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 정수 $n$, $m$, $k$가 주어진다.

이어지는 $m$개의 줄에는 빈 문자열이 아닌 문자열이 하나씩 주어진다. 이 문자열은 처음 $k$개의 소문자로 이루어져 있으며, 한 철도의 역들을 순서대로 나타낸다.

각 테스트 케이스마다 "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 \times 10^6$을 넘지 않는다.
• $k > 8$인 테스트 케이스는 최대 5개이다.