منذ زمن بعيد جدًا، كان في مملكة ما $n$ مدينة و$m$ خط سكة حديد. كان كل خط يضم مدنًا كثيرة، وكانت كل مدينة تقع على خط واحد بالضبط. ولأن بعض المدن لم تكن متصلة بخط سكة حديد، كان الناس كثيرًا ما يخوضون رحلة شاقة للانتقال من مدينة إلى أخرى. وقد أعاقت صعوبة المواصلات تطور اقتصاد المملكة بشدة، لذلك سرعان ما قرر الملك إطلاق عدة مسارات جوية.

بأمره، قُسّمت المدن إلى $k$ مناطق، فأصبح بالإمكان السفر بمناطيد الهواء الساخن بين أي مدينتين تنتميان إلى المنطقة نفسها. علاوة على ذلك، عند الرغبة في السفر إلى أي مدينة أخرى، كان بإمكان سكان المملكة الجمع بين القطارات ومناطيد الهواء الساخن دون استخدام أي وسائل نقل أخرى، وكان ذلك أيضًا أحد أسباب استمرار ازدهار الاقتصاد.

أراد الملك معرفة ما إذا كانت سياسته قد أفادت الجميع. لكنه لم يعرف الإجابة قبل وفاته، لأن الأمر كان يتطلب قدرًا هائلًا من الحسابات. والآن، بعدما تحسنت القدرة الحاسوبية، طُرحت المسألة من جديد. بافتراض أن الانتقال مباشرة بمنطاد هواء ساخن من مدينة إلى أخرى يستغرق ساعة واحدة، وأن الانتقال من مدينة إلى مدينة مجاورة على خط سكة حديد يستغرق ساعة واحدة أيضًا، يُطلب منك تحديد متوسط الزمن اللازم للسفر من مدينة إلى أخرى باستخدام هاتين الوسيلتين فقط، ثم إعطاء حاصل ضرب $\frac{n(n-1)}{2}$ في ذلك المتوسط، والذي ينبغي أن يكون عددًا صحيحًا.

لتجنب بيانات إدخال ضخمة، تُمثَّل كل مدينة بأحد الأحرف الصغيرة الـ $k$ الأولى، الذي يمثل محطة على خط سكة حديد، بحيث تكون المدن الممثلة بالحرف نفسه في المنطقة نفسها.

الإدخال

يحتوي الإدخال على عدة حالات اختبار. يحتوي السطر الأول على عدد صحيح $T$ يشير إلى عدد حالات الاختبار. فيما يلي وصف جميع حالات الاختبار. لكل حالة:

يحتوي السطر الأول على ثلاثة أعداد صحيحة $n$ و$m$ و$k$.

يحتوي كل سطر من الأسطر الـ $m$ التالية على سلسلة غير فارغة تتكون من الأحرف الصغيرة الـ $k$ الأولى، وتصف محطات خط سكة حديد بالترتيب.

• $1 \le T \le 1000$
• $1 \le m \le n \le 10^6$
• $1 \le k \le 16$
• تحتوي كل منطقة على مدينة واحدة على الأقل.
• لا يتجاوز مجموع $n$ في جميع حالات الاختبار $5 \times 10^6$.
• توجد 5 حالات اختبار على الأكثر تحقق $k > 8$.

الإخراج

لكل حالة اختبار، اطبع سطرًا يحتوي على Case #x: y (دون علامات الاقتباس)، حيث $x$ هو رقم حالة الاختبار بدءًا من 1، و$y$ هو جواب هذه الحالة (بالساعات).

أمثلة

الإدخال 1

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

الإخراج 1

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