FRAKTAL - konkurs programistyczny

Trzyliterówka

Jasiu wymyślił nową łamigłówkę. Mając wyrazy trzyliterowe, należy wszystkie połączyć tak, aby pierwsza litera wyrazu następnego była ostatnią literą wyrazu poprzedzającego. Mając trzy wyrazy: tik tak kot, można je dopasować np. tak: tikotak, co prowadzi do rozwiązania łamigłówki.
Zaczął więc Jasiu tworzyć zestawy haseł, gdy pomyślał, że szybciej będzie generować je programem. Napisał więc program i zauważył, że losowe hasła często nie rozwiązują łamigłówki, a tak być nie może. Napisał nowy program, który wyłonić miał spośród wygenerowanych zestawów te poprawne. No tak, miał, bo program do dzisiaj nie zakończył działania. Pomóż Jasiowi i napisz program, który wskaże zestawy haseł prowadzące do rozwiązania trzyliterówki.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych. Każdy zestaw danych opisany jest w dwóch wierszach. W pierwszym podana jest liczba całkowita n (1 ≤ n ≤ 100000) określająca liczbę haseł. W wierszu drugim podanych jest n trzyliterowych haseł złożonych z małych liter alfabetu łacińskiego.

Wyjście
Dla każdego zestawu danych należy wypisać albo słowo TAK, jeśli istnieje co najmniej jeden sposób prowadzący do rozwiązania łamigłówki, albo słowo NIE, jeśli nie jest to możliwe.

Przykład

Wejście
3
2
ten kot
3
tik tak kot
4
kto kot kat tok

Wyjście
TAK
TAK
NIE