Hace mucho, mucho tiempo, había $n$ ciudades y $m$ ferrocarriles en un reino. Cada ferrocarril incluía muchas ciudades, y cada ciudad estaba situada en exactamente un ferrocarril. Como algunas ciudades no estaban conectadas por ferrocarril, la gente solía afrontar un viaje arduo para ir de una ciudad a otra. Las dificultades de transporte habían frenado enormemente el desarrollo económico del reino, por lo que su rey pronto decidió abrir varias rutas aéreas.

Bajo sus órdenes, las ciudades se dividieron en $k$ distritos, de modo que se podía viajar en globo aerostático entre cualesquiera dos ciudades del mismo distrito. Además, para viajar a cualquier otra ciudad, los habitantes podían combinar trenes y globos aerostáticos sin utilizar ningún otro medio de transporte, lo que también contribuyó a que la economía siguiera prosperando.

El rey quería saber si su política había beneficiado a todo el mundo. Sin embargo, murió sin averiguarlo, pues se requería una enorme cantidad de cálculos. Ahora que la capacidad de cálculo ha mejorado, se vuelve a plantear el problema. Suponiendo que viajar directamente de una ciudad a otra en globo aerostático tarda una hora, y viajar de una ciudad a una ciudad adyacente por ferrocarril también tarda una hora, debes determinar el tiempo medio necesario para viajar de una ciudad a otra usando únicamente estos dos medios de transporte y comunicar el producto de $\frac{n(n-1)}{2}$ por dicho valor medio. El producto debería ser un entero.

Para evitar una entrada enorme, cada ciudad se representa mediante una de las primeras $k$ letras minúsculas, que representa una estación de un ferrocarril, de modo que las ciudades representadas por la misma letra pertenecen al mismo distrito.

Entrada

La entrada contiene varios casos de prueba. La primera línea contiene un entero $T$ que indica el número de casos. A continuación se describen todos los casos de prueba. Para cada caso:

La primera línea contiene tres enteros $n$, $m$ y $k$.

Cada una de las siguientes $m$ líneas contiene una cadena no vacía formada por las primeras $k$ letras minúsculas, que describe en orden las estaciones de un ferrocarril.

• $1 \le T \le 1000$
• $1 \le m \le n \le 10^6$
• $1 \le k \le 16$
• Cada distrito contiene al menos una ciudad.
• La suma de $n$ en todos los casos de prueba no supera $5 \times 10^6$.
• Hay como máximo 5 casos de prueba con $k > 8$.

Salida

Para cada caso de prueba, imprime una línea con Case #x: y (sin comillas), donde $x$ es el número del caso, comenzando por 1, e $y$ es la respuesta (en horas) para ese caso.

Ejemplos

Entrada 1

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

Salida 1

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