Vor langer, langer Zeit gab es in einem Königreich $n$ Städte und $m$ Eisenbahnlinien. Jede Eisenbahnlinie umfasste viele Städte, und jede Stadt lag an genau einer Eisenbahnlinie. Da manche Städte nicht durch eine Eisenbahnlinie verbunden waren, mussten die Menschen für Reisen von einer Stadt zur anderen oft beschwerliche Wege auf sich nehmen. Die ungünstigen Verkehrsverhältnisse behinderten die wirtschaftliche Entwicklung des Königreichs stark, weshalb der König bald beschloss, mehrere Flugrouten einzurichten.

Auf seine Anweisung wurden die Städte in $k$ Bezirke eingeteilt, sodass die Menschen zwischen je zwei Städten desselben Bezirks mit Heißluftballons reisen konnten. Außerdem konnten die Bewohner jede andere Stadt durch eine Kombination aus Zügen und Heißluftballons erreichen, ohne andere Verkehrsmittel zu benutzen. Auch das war ein Grund für den anhaltenden wirtschaftlichen Aufschwung.

Der König wollte wissen, ob seine Politik allen zugutegekommen war. Wegen der enormen erforderlichen Rechenarbeit fand er dies jedoch vor seinem Tod nicht heraus. Da die Rechenleistung inzwischen besser ist, wird das Problem nun erneut aufgegriffen. Angenommen, eine direkte Fahrt mit dem Heißluftballon von einer Stadt in eine andere dauert eine Stunde, und eine Fahrt von einer Stadt zur benachbarten Stadt an einer Eisenbahnlinie dauert ebenfalls eine Stunde. Bestimme die durchschnittlich benötigte Reisezeit von einer Stadt zu einer anderen, wenn nur diese beiden Verkehrsmittel verwendet werden, und gib dann das Produkt aus $\frac{n(n-1)}{2}$ und diesem Durchschnittswert an; dieses sollte eine ganze Zahl sein.

Um riesige Eingabedaten zu vermeiden, wird jede Stadt durch einen der ersten $k$ Kleinbuchstaben dargestellt, der eine Station an einer Eisenbahnlinie bezeichnet. Städte mit demselben Buchstaben liegen im selben Bezirk.

Eingabe

Die Eingabe enthält mehrere Testfälle. Die erste Zeile enthält eine ganze Zahl $T$, die die Anzahl der Testfälle angibt. Im Folgenden werden alle Testfälle beschrieben. Für jeden Testfall gilt:

Die erste Zeile enthält drei ganze Zahlen $n$, $m$ und $k$.

Jede der folgenden $m$ Zeilen enthält eine nicht leere Zeichenkette aus den ersten $k$ Kleinbuchstaben, die die Stationen einer Eisenbahnlinie in ihrer Reihenfolge beschreibt.

• $1 \le T \le 1000$
• $1 \le m \le n \le 10^6$
• $1 \le k \le 16$
• Jeder Bezirk enthält mindestens eine Stadt.
• Die Summe von $n$ über alle Testfälle überschreitet $5 \times 10^6$ nicht.
• Es gibt höchstens 5 Testfälle mit $k > 8$.

Ausgabe

Gib für jeden Testfall eine Zeile mit Case #x: y (ohne Anführungszeichen) aus, wobei $x$ die bei 1 beginnende Testfallnummer und $y$ die Antwort (in Stunden) für diesen Testfall ist.

Beispiele

Eingabe 1

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

Ausgabe 1

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