시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB0000.000%

문제

Naukowcy w Królestwie Bajtlandii postanowili stworzyć nowy rodzaj komputerów, a mianowice komputery trzybitowe (KTB). Powszechnie uważa się, że ten nowy rodzaj komputerów pozwoli rozwiązać wiele problemów zbyt trudnych dla klasycznych komputerów. Niestety, w trakcie prac naukowcy napotkali wiele trudności technicznych. Twoim zadaniem jest pomóc im w przezwyciężeniu jednej z nich.

Naukowcy zajmują się aktualnie procedurami inicjalizacji pamięci komputera. Komputer KTB posiada n bitów pamięci ponumerowanych liczbami 1,…,n. Każdy bit może przyjmować jedną z trzech wartości a,b,c lub być w stanie niezainicjalizowanym. Komputer KTB udostępnia następujące operacje inicjalizujące:

  • dwóm kolejnym niezainicjalizowanym bitom można przypisać dwie różne wartości,
  • dwóm kolejnym bitom, z których jeden jest niezainicjalizowany, a drugi ma wartość x, można przypisać dwie różne wartości, przy czym obie muszą być różne od x.

Oto przykładowa sekwencja inicjalizacji pamięci dla n=4: uuuu -> uuab -> ucbb -> babb, gdzie u oznacza bit niezainicjalizowany.

Zadanie

Napisz program, który:

  • wczyta wartości, którymi ma być zainicjalizowana pamięć,
  • sprawdzi czy taka inicjalizacja jest możliwa,
  • wypisze znalezioną odpowiedź.

입력

Standardowe wejście może zawierać opisy od 1 do 10 konfiguracji pamięci, które chcemy uzyskać. Pierwszy wiersz wejścia zawiera pojedynczą liczbę całkowitą - liczbę konfiguracji. W kolejnych wierszach znajdują się opisy konfiguracji. Opis jednej konfiguracji składa się z dwóch wierszy. Pierwszy wiersz zawiera pojedynczą liczbę całkowitą  li, (1 ≤ li ≤ 100000), rozmiar pamięci dla i-tej konfiguracji. Drugi wiersz zawiera ciąg długości li składający się z liter a,b,c - ciąg ten opisuje konfigurację, którą chcemy uzyskać.

 

출력

Standardowe wyjście powinno zawierać N wierszy, po jednym dla każdej konfiguracji pamięci. i-ty wiersz powinien zawierać pojedyncze słowo TAK, jeśli inicjalizacja jest możliwa, w przeciwnym przypadku NIE.

 

예제 입력 1

2
4
aaab
4
aabb

예제 출력 1

TAK
NIE

출처

Camp > POI Training Camp > ONTAK 2008 2-1번