นานมาแล้ว มีเมือง $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$
• มีกรณีทดสอบที่ $k > 8$ ไม่เกิน 5 กรณี

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้พิมพ์หนึ่งบรรทัดที่มี 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