Archiwum zadań programistycznych WWSI

Zapewne wszyscy z Was znają grę w węża, która to była jedną z najpopularniejszych gier dla telefonów komórkowych. Gra w ostatnich czasach mocno się rozwinęła uzyskując nową funkcjonalność: 3D, multiplayer itp. My jednak zajmiemy się starym dobrym dwuwymiarowym wężem znanym chociażby z Nokii 3210. Otóż nasz wąż porusza się po nieskończenie dużej planszy. Z każdej z jej komórek możemy skręcić w prawo, w lewo albo pójść prosto. Oczywiście nasz wąż może też zjadać znajdujące się na planszy elementy, w końcu na tym polega ta gra aby spożyć ich jak najwięcej. Zjedzenie jednego elementu powoduje wydłużenie się węża o ten właśnie element np. wąż znajdujący się na polach 0 0 (głowa), 1 0, 2 0 zjada element znajdujący się na polu -1 0, po zjedzeniu wąż składa się z pól -1 0 (głowa), 0 0, 1 0, 2 0. Twoim zadaniem będzie sprawdzenie na podstawie wczytanych na wejściu ruchów węża czy gra zakończy się wraz z ostatnim ruchem czy też wąż zginie gryząc sam siebie. Początkowa długość węża wynosi 1.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 1000) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej i jedynej linii każdego zestawu danych znajduje się jedna liczba naturalna n (1 ≤ n ≤ 2400), określająca ilość ruchów jakie wykona wąż oraz n znaków określających te ruchy. Każdy znak to jedna z czterech liter: L, R, F, albo E. L - wąż przechodzi na pole po swojej lewej stronie, R - wąż przechodzi na pole po swojej prawej stronie, F - wąż przechodzi na pole przed sobą, E - wąż przechodzi na pole przed sobą i zjada znajdujący się na nim element.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać słowo "TAK" jeżeli wąż przejdzie zwycięsko grę albo numer porządkowy ruchu w którym ugryzł samego siebie. Numerację ruchów zaczynamy od 1.

Przykład

Wejście:

2
6 FLERFF
8 EEEELLLL

Wyjście:

TAK
7