AlgoLiga 2018

Seki

Do rozwiązania tego zadania potrzebne jest zapoznanie się z regułami gry go.
Więcej informacji o grze go znajdziesz na stronie go.art.pl/.

Jako zadanie, dla każdego przypadku testowego, dostaniesz zakończoną partię go w postaci diagramu n × n. Twój program musi rozstrzygnąć, czy na planszy występuje co najmniej jedno seki, czyli lokalna sytuacja, w której żyją piony obu stron pomimo tego, że nie posiadają dwóch oczu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 100). Pierwszy wiersz każdego przypadku testowego to liczba n (9 ≤ n ≤ 19) oznaczająca rozmiar diagramu. Każdy diagram składa się z n wierszy, po n znaków w każdym wierszu i przedstawia planszę n × n po zakończonej rozgrywce w go. Każdy diagram opisany jest za pomocą trzech znaków:
- znak "." (kropki) to puste skrzyżowanie linii na planszy,
- znak "x" oznacza, że na przecięciu linii znajduje się kamień czarny,
- znak "o" oznacza, że na przecięciu linii znajduje się kamień biały,
Wszystkie sytuacje przedstawione na diagramach w wejściu są zgodne ze sztuką gry w go.

Wyjście
Na wyjściu, dla każdego przypadku testowego należy wypisać słowo TAK, jeśli na planszy występuje co najmniej jedno seki, w przeciwnym przypadku należy wypisać słowo NIE.

Przykład

Wejście
2
9
.oxxooxx.
.ox.xox.x
.ox.xoxxo
.ox.xoxoo
oox.xooo.
xxxxoo...
.xooxo.o.
.xo.xo...
.xo.xo...
9
..oooxx..
oo..oox..
xoooxox..
xxoxxx.x.
.xox.x...
.xxxooxx.
..xo.ooxx
x.xo.o.ox
.xoo..ooo

Wyjście
TAK
NIE