遠い昔、ある王国には $n$ 個の都市と $m$ 本の鉄道がありました。各鉄道には多くの都市があり、各都市はちょうど 1 本の鉄道上にありました。鉄道でつながっていない都市もあったため、ある都市から別の都市へ移動する際、人々はしばしば困難な旅を強いられました。交通の不便さは王国の経済発展を大きく妨げていたので、王はやがていくつかの航空路線を開設することにしました。

王の指示により、都市は $k$ 個の地区に分けられ、同じ地区に属する任意の 2 都市間を熱気球で移動できるようになりました。さらに、王国の人々は任意の他の都市へ行くとき、他の交通手段を使わず、列車と熱気球の組み合わせだけで移動できるようになりました。これも経済が繁栄し続けた理由の一つでした。

王は自分の政策がすべての人の利益になったのか知りたいと思っていました。しかし、膨大な計算が必要だったため、亡くなるまでに答えを得られませんでした。計算能力が向上した今、この問題が再び取り上げられました。ある都市から別の都市へ熱気球で直接移動するのに 1 時間、鉄道上の隣接する都市へ移動するのにも 1 時間かかると仮定します。この 2 種類の交通手段だけを使って、ある都市から別の都市へ移動するのに必要な時間の平均を求め、$\frac{n(n-1)}{2}$ とその平均値の積を出力してください。この積は整数になるはずです。

入力データが膨大になるのを避けるため、各都市は最初の $k$ 個の英小文字のいずれかで表され、鉄道上の駅を表します。同じ文字で表された都市は同じ地区に属します。

入力

入力は複数のテストケースからなります。最初の行にはテストケース数を表す整数 $T$ が含まれます。以下で全テストケースについて説明します。各テストケースについて：

最初の行には 3 つの整数 $n$、$m$、$k$ が含まれます。

続く $m$ 行のそれぞれには、最初の $k$ 個の英小文字からなる空でない文字列が含まれ、ある鉄道の駅を順に表します。

• $1 \le T \le 1000$
• $1 \le m \le n \le 10^6$
• $1 \le k \le 16$
• 各地区には少なくとも 1 つの都市があります。
• 全テストケースにおける $n$ の総和は $5 \times 10^6$ 以下です。
• $k > 8$ を満たすテストケースは高々 5 個です。

出力

各テストケースについて、Case #x: y（引用符を除く）を含む 1 行を出力してください。ここで $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