Dawno, dawno temu w pewnym królestwie było $n$ miast i $m$ linii kolejowych. Każda linia obejmowała wiele miast, a każde miasto leżało na dokładnie jednej linii. Ponieważ niektóre miasta nie były połączone linią kolejową, podróż z jednego miasta do drugiego często była uciążliwa. Niewygodny transport znacznie hamował rozwój gospodarczy królestwa, więc jego król wkrótce postanowił uruchomić kilka tras powietrznych.

Na jego polecenie miasta podzielono na $k$ okręgów, dzięki czemu można było podróżować balonami na ogrzane powietrze między dowolnymi dwoma miastami w tym samym okręgu. Ponadto mieszkańcy mogli dotrzeć do dowolnego innego miasta, łącząc przejazdy pociągami i loty balonami, bez korzystania z innych środków transportu. Był to również jeden z powodów dalszego rozkwitu gospodarki.

Król chciał wiedzieć, czy jego polityka przyniosła korzyści wszystkim. Nie dowiedział się tego jednak przed śmiercią, ponieważ wymagało to ogromnej liczby obliczeń. Teraz, gdy możliwości obliczeniowe są większe, ponownie podjęto ten problem. Zakładając, że bezpośredni lot balonem z jednego miasta do drugiego trwa godzinę, a przejazd z miasta do sąsiedniego miasta na linii kolejowej również trwa godzinę, wyznacz średni czas potrzebny na podróż z jednego miasta do drugiego przy użyciu wyłącznie tych dwóch środków transportu, a następnie podaj iloczyn $\frac{n(n-1)}{2}$ i tej średniej wartości, który powinien być liczbą całkowitą.

Aby uniknąć ogromnych danych wejściowych, każde miasto jest reprezentowane przez jedną z pierwszych $k$ małych liter, oznaczającą stację na linii kolejowej. Miasta reprezentowane tą samą literą należą do tego samego okręgu.

Wejście

Wejście zawiera kilka przypadków testowych. Pierwszy wiersz zawiera liczbę całkowitą $T$, oznaczającą liczbę przypadków testowych. Poniżej opisano wszystkie przypadki. Dla każdego przypadku:

Pierwszy wiersz zawiera trzy liczby całkowite $n$, $m$ i $k$.

Każdy z kolejnych $m$ wierszy zawiera niepusty napis złożony z pierwszych $k$ małych liter, opisujący po kolei stacje jednej linii kolejowej.

• $1 \le T \le 1000$
• $1 \le m \le n \le 10^6$
• $1 \le k \le 16$
• Każdy okręg zawiera co najmniej jedno miasto.
• Suma $n$ we wszystkich przypadkach testowych nie przekracza $5 \times 10^6$.
• Istnieje co najwyżej 5 przypadków testowych z $k > 8$.

Wyjście

Dla każdego przypadku testowego wypisz wiersz zawierający Case #x: y (bez cudzysłowów), gdzie $x$ jest numerem przypadku testowego, zaczynającym się od 1, a $y$ jest odpowiedzią (w godzinach) dla tego przypadku.

Przykład

Wejście 1

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

Wyjście 1

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