Diagram krzyżówki ma kształt kwadratu i składa się z N2 pól - N pól w wierszu oraz N pól w kolumnie. Wyrazy do diagramu wpisywane są na dwa sposoby - w wierszu od strony lewej do prawej oraz w kolumnie z góry w dół. Wyrazy znajdujące się w wierszach mogą krzyżować się z wyrazami znajdującymi się w kolumnach, przy czym w miejscu skrzyżowania musi zachodzić zgodność liter. Oprócz zgodności liter wymagane jest także, aby krzyżującą się literą nie była pierwsza i ostatnia litera wyrazu.
Niech będą dane 4 wyrazy o identycznej długości:
BAABAABAABAB BABAABABBAAB BABABAAABAAB BBAABAABBAAB
Do diagramu krzyżówki zostaną wpisane dwa wyrazy w wierszu i dwa w kolumnie w taki sposób, aby krzyżowały się tworząc zamknięty obszar. Wielkość obszaru (mierzona liczbą pól znajdujacych się wewnątrz) jest zależna od sposobu wpisania wyrazów. Na rysunku przedstawiono dwa przykładowe sposoby wpisania wyrazów do diagramu. Na rysunku A rozmiar obszaru zamkniętego jest równy 56, natomiast na rysunku B jest on równy 6.
A) B) B B B B BBAABAABBAAB A B B B B A A A A A A B BAABAABAABAB B A A A A A A A B A A B B B BABAABABBAAB A A A A BAABAABAABAB A A B B B B
Twoim zadaniem jest napisanie programu, który dla zadanych czterech wyrazów, wyznaczy jaki jest maksymalny rozmiar obszaru zamkniętego utworzonego w sposób opisany powyżej.
W pierwszym wierszu znajduje się liczba K będąca liczbą zestawów danych wejściowych.
Pojedynczy zestaw danych składa się z czterech wierszy zawierających wyrazy. Każdy wyraz składa się z 12 liter i zawiera wyłącznie duże litery z zakresu A, ..., P.
Dane wyjściowe składają się z K wierszy. Jeden wiersz odpowiada jednemu zestawowi danych i zawiera maksymalny rozmiar obszaru zamkniętego.
3 AAAAAAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAA BAABAABAABAB BABAABABBAAB BABABAAABAAB BBAABAABBAAB CDBADCBBEFEF DACCBADAFEAB EFBDCAADBDCD ABCDABCDABCD
64 56 48