Давним-давно в одному королівстві було $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