Problem II: Mrówki

Treść

Na wyspach Pitu-Pitu, pośród wielu ciekawych i nigdzie indziej niespotykanych stworzeń, żyją mrówki łamigłówki. Stawonogi te mają wiele niespotykanych wśród swych europejskich krewnych zwyczajów. Jednym z nich są doroczne tańce robotnic. Obrządek ten ma ściśle ustaloną i przestrzeganą procedurę. Co roku każde mrowisko wystawia jednakową liczbę kolorowo ubranych tancerzy. Taniec rozpoczyna się od ustawienia się mrówek w szeregu. W takiej pozycji mrówki stoją przez jakiś czas śpiewając swój narodowy hymn. Następnie początek szeregu podąża wokół mrowiska łącząc się z końcem, tworząc w ten sposób wielobarwny okrąg.

Początkowe ustawienie mrówek jest niezwykle istotne dla całej pitu-pituńskiej populacji. Jeżeli bowiem okręgi utworzone przez wszystkie mrowiska są identyczne pod względem kolorów strojów kolejnych tancerzy, to w przyszłym roku mrówki się rozmnożą i utworzą nowe mrowisko. Naukowcy badający zachowanie mrówek łamigłówek mają niełatwy orzech do zgryzienia, gdyż tańczące mrówki bardzo szybko się poruszają i trudno jest stwierdzić czy okręgi dla wszystkich mrowisk są jednakowe. Na szczęście w czasie śpiewania hymnu udało się zrobić zdjęcia. Na ich podstawie przyrodnicy próbują teraz stwierdzić, czy utworzone okręgi będą identyczne i czy w przyszłym roku przybędzie mrowisk na wyspach. Pomóż im i napisz program, który zautomatyzuje cały proces i możliwie szybko da właściwą odpowiedź.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu zawiera dwie liczby całkowite n oraz m (2<=n<=10, 2<=m<=100 000), oddzielone spacją, oznaczające kolejno liczbę mrowisk na wyspach i liczbę tancerzy w każdym z nich. Kolejnych n wierszy opisuje początkowe szeregi mrówek dla kolejnych mrowisk. Pojedynczy szereg składa się z ciągu cyfr (od 0 do 9). Każda cyfra odpowiada innemu kolorowi. Wszystkie szeregi liczą sobie po m cyfr.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest wyraz TAK, jeżeli okręgi utworzone przez wszystkie mrowiska są identyczne i wyraz NIE w przeciwnym wypadku.

Przykład

dane wejściowe:
2
2 4
7889
9788
3 4
1223
2312
3121

wynik:
TAK
NIE