Pada zaman dahulu kala, terdapat $n$ kota dan $m$ jalur kereta api di sebuah kerajaan. Setiap jalur mencakup banyak kota, dan setiap kota terletak pada tepat satu jalur kereta api. Karena beberapa kota tidak terhubung oleh jalur kereta api, orang sering menempuh perjalanan yang sulit saat berpindah dari satu kota ke kota lain. Transportasi yang tidak nyaman sangat menghambat perkembangan ekonomi kerajaan, sehingga raja segera memutuskan membuka beberapa rute udara.

Atas arahannya, kota-kota dibagi menjadi $k$ distrik, sehingga orang dapat bepergian dengan balon udara panas antara sembarang dua kota dalam distrik yang sama. Selain itu, saat hendak pergi ke kota lain mana pun, penduduk dapat menggunakan kombinasi kereta api dan balon udara panas tanpa moda transportasi lain, yang juga menjadi salah satu alasan ekonomi terus berkembang.

Raja ingin mengetahui apakah kebijakannya telah menguntungkan semua orang. Namun, ia tidak mendapatkan jawabannya sebelum meninggal karena diperlukan perhitungan yang sangat banyak. Kini kemampuan komputasi telah meningkat, sehingga persoalan itu kembali diajukan. Dengan asumsi perjalanan langsung dari satu kota ke kota lain menggunakan balon udara panas memerlukan satu jam, dan perjalanan dari satu kota ke kota yang bersebelahan pada jalur kereta api juga memerlukan satu jam, Anda diminta menentukan rata-rata waktu yang diperlukan untuk bepergian dari satu kota ke kota lain hanya dengan kedua moda tersebut, lalu melaporkan hasil kali $\frac{n(n-1)}{2}$ dengan nilai rata-rata itu. Hasil kali tersebut seharusnya berupa bilangan bulat.

Untuk menghindari data masukan yang sangat besar, setiap kota diwakili oleh salah satu dari $k$ huruf kecil pertama, yang menyatakan sebuah stasiun pada jalur kereta api. Kota-kota yang diwakili oleh huruf yang sama berada dalam distrik yang sama.

Masukan

Masukan berisi beberapa kasus uji. Baris pertama berisi bilangan bulat $T$ yang menyatakan banyaknya kasus uji. Berikut adalah deskripsi semua kasus uji. Untuk setiap kasus:

Baris pertama berisi tiga bilangan bulat $n$, $m$, dan $k$.

Setiap baris dari $m$ baris berikutnya berisi string tidak kosong yang terdiri atas huruf-huruf dari $k$ huruf kecil pertama, yang menjelaskan stasiun pada satu jalur kereta api secara berurutan.

• $1 \le T \le 1000$
• $1 \le m \le n \le 10^6$
• $1 \le k \le 16$
• Setiap distrik memuat sedikitnya satu kota.
• Jumlah $n$ pada semua kasus uji tidak melebihi $5 \times 10^6$.
• Terdapat paling banyak 5 kasus uji dengan $k > 8$.

Keluaran

Untuk setiap kasus uji, cetak satu baris berisi Case #x: y (tanpa tanda kutip), dengan $x$ adalah nomor kasus uji mulai dari 1, dan $y$ adalah jawaban (dalam jam) untuk kasus tersebut.

Contoh

Masukan 1

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

Keluaran 1

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