#include <iostream>
#include <algorithm>
bool czy_dobrze(int tab[2][1000], int i, int rozmiar)
{
for (int j=i-rozmiar; j<i; j++)
{
if((tab[0][j] == tab[0][i]) && (tab[1][j] == tab [1][i]))
return false;
}
return true;
}
void zmien (int &jak, int &px, int &py, int i)
{
using std::swap;
jak=jak%2;
if (jak==i)
{
px*=-1;
py*=-1;
}
swap (px,py);
}
void ruch(int poz[2][1000], int px, int py, int i)
{
poz [0][i]=poz[0][i-1]+px;
poz [1][i]=poz[1][i-1]+py;
}
int main()
{
using namespace std;
string q;
int tab[2][1000];
tab[0][0]=0;
tab[1][0]=0;
int px=1;
int py=0; //poczatkowy kierunek ruchu
int rozmiar;
int orient = 1;
char akcja;
int razy,ile;
cin >> ile;
for (int k=0; k < ile; k++)
{
cin >> razy;
rozmiar = 0;
for (int i = 1; i <= razy; i++)
{
cin>>akcja;
switch (akcja)
{
case 'L':
{
zmien(orient,px,py,0);
orient++;
break;
}
case 'R':
{
zmien(orient,px,py,1);//zmiana kierunku przy skrecie w prawo
orient++;
break;
}
case 'E': rozmiar++ ; break;
}
ruch(tab,px,py,i);
if (!czy_dobrze(tab,i,rozmiar))
{
if (i<razy)cin >> q;
cout << i <<endl;
break;
}
if(i == razy) cout << "TAK" << endl;
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKYm9vbCBjenlfZG9icnplKGludCB0YWJbMl1bMTAwMF0sIGludCBpLCBpbnQgcm96bWlhcikKewogICAgZm9yIChpbnQgaj1pLXJvem1pYXI7IGo8aTsgaisrKQogICAgewogICAgICAgIGlmKCh0YWJbMF1bal0gPT0gdGFiWzBdW2ldKSAmJiAodGFiWzFdW2pdID09IHRhYiBbMV1baV0pKQogICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9CiAgICByZXR1cm4gdHJ1ZTsKfQoKdm9pZCB6bWllbiAoaW50ICZqYWssIGludCAmcHgsIGludCAmcHksIGludCBpKQp7CiAgICB1c2luZyBzdGQ6OnN3YXA7CiAgICBqYWs9amFrJTI7CiAgICBpZiAoamFrPT1pKQogICAgewogICAgICAgIHB4Kj0tMTsKICAgICAgICBweSo9LTE7CgogICAgfQogICAgc3dhcCAocHgscHkpOwp9Cgp2b2lkIHJ1Y2goaW50IHBvelsyXVsxMDAwXSwgaW50IHB4LCBpbnQgcHksIGludCBpKQp7CiAgICBwb3ogWzBdW2ldPXBvelswXVtpLTFdK3B4OwogICAgcG96IFsxXVtpXT1wb3pbMV1baS0xXStweTsKfQoKaW50IG1haW4oKQp7CiAgICB1c2luZyBuYW1lc3BhY2Ugc3RkOwogICAgc3RyaW5nIHE7CiAgICBpbnQgdGFiWzJdWzEwMDBdOwogICAgdGFiWzBdWzBdPTA7CiAgICB0YWJbMV1bMF09MDsKICAgIGludCBweD0xOwogICAgaW50IHB5PTA7IC8vcG9jemF0a293eSBraWVydW5layBydWNodQogICAgaW50IHJvem1pYXI7CiAgICBpbnQgb3JpZW50ID0gMTsKICAgIGNoYXIgYWtjamE7CiAgICBpbnQgcmF6eSxpbGU7CiAgICBjaW4gPj4gaWxlOwogICAgZm9yIChpbnQgaz0wOyBrIDwgaWxlOyBrKyspCiAgICB7CiAgICAgICAgY2luID4+IHJhenk7CiAgICAgICAgcm96bWlhciA9IDA7CiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gcmF6eTsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgY2luPj5ha2NqYTsKICAgICAgICAgICAgc3dpdGNoIChha2NqYSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgY2FzZSAnTCc6CiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICB6bWllbihvcmllbnQscHgscHksMCk7CiAgICAgICAgICAgICAgICAgICAgICAgIG9yaWVudCsrOwogICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBjYXNlICdSJzoKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHptaWVuKG9yaWVudCxweCxweSwxKTsvL3ptaWFuYSBraWVydW5rdSBwcnp5IHNrcmVjaWUgdyBwcmF3bwogICAgICAgICAgICAgICAgICAgICAgICBvcmllbnQrKzsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgY2FzZSAnRSc6IHJvem1pYXIrKyA7IGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHJ1Y2godGFiLHB4LHB5LGkpOwogICAgICAgICAgICBpZiAoIWN6eV9kb2JyemUodGFiLGkscm96bWlhcikpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChpPHJhenkpY2luID4+IHE7CiAgICAgICAgICAgICAgICBjb3V0IDw8IGkgPDxlbmRsOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYoaSA9PSByYXp5KSBjb3V0IDw8ICJUQUsiIDw8IGVuZGw7CiAgICAgICAgfQoKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=