12444번 - アンテナ修復 (Large) 스페셜 저지다국어

冒険家のパスカルは古代文明が残した宇宙人との通信装置を発見し使用方法を解明した。装置のアンテナは K 本のエレメントと呼ばれる特殊物質でできた直線状の棒で構成される。各エレメントの一端は + 極と呼ばれ、もう一端は - 極と呼ばれる。エレメントには 1 から K までの番号が振られている。

アンテナを動作させるには以下の4つの条件を満たすように組み立てなければならない。

• すべてのエレメントが同一平面上にある
• すべてのエレメントの + 極が同じ位置にある。これを接続点と呼ぶ
• エレメント同士が重なるのは接続点のみ
• 隣り合うエレメントがなす角度はすべて 360/K 度である

隣り合うエレメントの - 極の位置 2 点と接続点で作られる三角形の面積を隣り合うエレメントの組み合わせすべてについて足しあわせた値がアンテナの強度となる。

アンテナの強度を最大化する並べ方を計算し、その強度を出力せよ。

エレメントの太さは無視できるほど細いものとする。エレメントを切断したり、複数のエレメントをつなぎあわせて1本のエレメントとして使うことはできない。

最初の行はテストケースの個数 T を表す正の整数である。各テストケースは以下のようなフォーマットで表される。

K
E1 E2 ... EK

ここで K はエレメントの数である。E_i は正の整数で、i 番目のエレメントの長さを表している。

制約

• 1 ≤ T ≤ 100 
• 1 ≤ E_i ≤ 1000
• 3 ≤ K ≤ 1000

各テストケースに対し、

Case #X: P

という内容を1行出力せよ。X は 1 から始まるテストケース番号、P は最大化された強度を表す。