F - Sześcian

Po wielu latach badań grupa Merck wynalazła prosty model, który jest pomocny we wspomaganym komputerowo tworzeniu leków. Różne substancje chemiczne są reprezentowane jako dwuwymiarowe puzzle, które mogą być połączone w przestrzeni trójwymiarowej tworząc bardziej skomplikowane atomy. Pewne szczególne kombinacje tych kawałków posiadają szczególne właściwości chemiczne. Takie specjalne kombinacje formowane są przez połączenie sześciu kawałków wzdłuż ich krawędzi w taki sposób, by stworzyły pełny sześcian.

Rys. 1 Konstrukcja sześcianu.

Zadanie

Mając dane sześć kawałków masz za zadanie określić czy mogą być złożone w taki sposób, by stworzyć sześcian o wymiarach 6 x 6 x 6, tak żeby nie pojawiła się żadna dziura widoczna z zewnątrz. O każdym elemencie można myśleć jako o wyciętym z kawałka drewna o wymiarze 6 x 6 x 1 z środkiem o wymiarze 4 x 4 x 1 nietkniętym. Element może być użyty w dowolnym położeniu, nie ma rozróżnienia pomiędzy stroną zewnętrzną i wewnętrzną kawałka.

Wejście

W pierwszej linii znajduje się liczba testów. W kolejnych sześciu liniach znajduje się graficzna reprezentacja sześciu części. Znak "X" symbolizuje drewno, znak "." symbolizuje wycięty kawałek o rozmiarze 1 x 1 x 1. Kolumna złożona z "!" oddziela pojedyncze kawałki od siebie. Po każdym teście następuje pusta linia.
Nie jest konieczne, aby kawałki wycięte z drewna tworzyły stabilną całość (Na przykład test drugi w przykładowym wejściu).

Wyjście

Dla każdego testu wypisz jedną linię z wyrazem "TAK", jeżeli zestaw kawałków może utworzyć sześcian lub jedną linię z wyrazem "NIE", jeżeli z zestawu nie da się utworzyc sześcianu.

Przykładowe wejście

Przykładowe wyjście