AlgoLiga 2018

Budynek Wydziału Matematyki, Informatyki i Mechaniki Uniwersytetu Bajtockiego (WMIMUB) składa się z n pięter ponumerowanych od 1 do n kolejno od najniższego do najwyższego. Pomiędzy nimi jeździ winda, która ostatnimi czasy zachowywała się dziwnie. Postanowiono zbadać przyczynę problemu i zajrzano w historię jej operacji. Historia ta składa się z ciągu liter U oraz D. Jeśli i-tą literą tego ciągu jest znak U to znaczy, że i-tą z kolei operacją windy była jazda w górę, jeśli jest to znak D to znaczy, że winda jechała wtedy w dół (w obu przypadkach o jedno piętro). Są jednak podejrzenia, że i z tym elementem windy jest coś nie tak. Należy jak najszybciej sprawdzić czy dana historia ma w ogóle sens. Przecież jeśli budynek ma 5 pięter to winda nie mogła jechać 10 razy w dół pod rząd.

Wejście

W pierwszej linii wejścia znajduje się liczba testów 0 < t ≤ 100. Następnie każdy test w oddzielnej linii. W pierwszym wierszu testu znajduje się liczba 1 < n ≤ 100, która oznacza liczbę pięter w budynku wydziału MIMUB. W następnym wierszu podana jest sekwencja ruchów, które po kolei winda wykonywała. Sekwencja ruchów składa się z co najwyżej 10⁵ znaków i co najmniej jednego.

Wyjście

Dla każdego testu wynik w osobnej linii. Wynikiem jest słowo TAK, jeśli dana sekwencja ruchów windy jest możliwa. W przeciwnym przypadku wynikiem jest słowo NIE.

Przykład

Wejście:
2
3
UUDDDU
4
DUDDU

Wyjście:
NIE
TAK

Wyjaśnienie do przykładu

W pierwszym teście budynek ma 3 piętra i nie ważne czy winda wystartuje z piętra o numerze 1, 2, czy też 3, bowiem zawsze zabraknie jednego piętra w piątym (czy też wcześniejszym) ruchu, aby przemieścić się o jedno piętro we wskazanym kierunku.

W drugim teście winda może wystartować z trzeciego piętra i odwiedzi kolejno piętra: 2, 3, 2, 1, 2.