時間制限:1000ミリ秒
メモリ制限:65536KB
問題
スモール・ジョンはサイコロを積み上げるゲームで遊んでいる。サイコロの6つの面はどれも同じ大きさの正方形である。サイコロのそれぞれの面には1から6の数字が書かれている。
サイコロ・ゲームは複数のサイコロを任意の順序で積み上げるゲームである。あなたは次のルールに従わなければならない：任意の2つの隣接したサイコロに対して、上のサイコロの底面の数字と下のサイコロの上面の数字は等しくなければならない。言い換えると、重なっている2つの面は同じ数字でなければならない。
そして、4つの側面を持つ長い長方形の柱が作られる。私たちは、ある側面が最大の和を持つようにしようとしている。（私たちがサイコロの上面と底面を固定したら、私たちがサイコロを90度、180度、270度回転させることができることに注意せよ。）ある側面が持ちうる、最大の和を求めるプログラムを作成せよ。
入力
入力の最初の行には、テストケースの数を表す整数tが書かれている。それに続いて各テストケースが示されている。各テストケースの最初の行には、サイコロの数を表す整数n(1<=n<=10)が書かれている。続く各行には、各サイコロの各面の数字を表す6つの整数が空白を区切りとして、上の図と同様にA,B,C,D,E,Fの順に書かれている。
出力
各テストケースごとに、ある側面が持ちうる最大の和を表す一つの整数を含む1行を出力せよ。もしすべてのサイコロを積み上げることが出来ないなら、「0」のみを1行に出力せよ。
入力の例
1 5 2 3 1 6 5 4 3 1 2 4 6 5 5 6 4 1 3 2 1 3 6 2 4 5 4 1 6 5 2 2
出力の例
30
出典
POJ Monthly--2005.08.28,Huang Ninghai