#include <iostream>
#include <list>
using namespace std;
int n,length,leb,kier,kaput,waz,check,ktoradead,rozkaz;
bool jem,zyje;
list <int> lista;
string data;
int main()
{
cin>>n;
for (int a=0;a<=n-1;a++)
{
cin>>length;
lista.push_front(1000010000);
leb=1000010000;
kier=1,jem=false,waz=1,zyje=true,ktoradead=0;
getline(cin,data);
for(int b=1;b<=length;b++)
{
rozkaz=data[b];
if(rozkaz==82)
{
kier++;
if(kier==5) kier=1;
}
else if(rozkaz==76)
{
kier--;
if(kier==0) kier=4;
}
else if(rozkaz==69) jem=true;
if(kier==1) leb++;
else if(kier==2) leb=leb+100000;
else if(kier==3) leb--;
else if(kier==4) leb=leb-100000;
if(jem!=true) lista.pop_back();
else jem=false;
waz=lista.size();
lista.remove(leb);
check=lista.size();
if (check+1<=waz)
{
ktoradead=b;
b=length;
zyje=false;
}
lista.push_front(leb);
}
if (zyje==true) cout<<"TAK"<<endl;
else cout<<ktoradead<<endl;
lista.clear();
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bGlzdD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG4sbGVuZ3RoLGxlYixraWVyLGthcHV0LHdheixjaGVjayxrdG9yYWRlYWQscm96a2F6Owpib29sIGplbSx6eWplOwpsaXN0IDxpbnQ+IGxpc3RhOwpzdHJpbmcgZGF0YTsKaW50IG1haW4oKQp7CiAgICBjaW4+Pm47CiAgICBmb3IgKGludCBhPTA7YTw9bi0xO2ErKykKICAgIHsKICAgICAgICBjaW4+Pmxlbmd0aDsKICAgICAgICBsaXN0YS5wdXNoX2Zyb250KDEwMDAwMTAwMDApOwogICAgICAgIGxlYj0xMDAwMDEwMDAwOwogICAgICAgIGtpZXI9MSxqZW09ZmFsc2Usd2F6PTEsenlqZT10cnVlLGt0b3JhZGVhZD0wOwogICAgICAgIGdldGxpbmUoY2luLGRhdGEpOwogICAgICAgIGZvcihpbnQgYj0xO2I8PWxlbmd0aDtiKyspCiAgICAgICAgewogICAgICAgICAgICByb3prYXo9ZGF0YVtiXTsKICAgICAgICAgICAgaWYocm96a2F6PT04MikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAga2llcisrOwogICAgICAgICAgICAgICAgaWYoa2llcj09NSkga2llcj0xOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYocm96a2F6PT03NikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAga2llci0tOwogICAgICAgICAgICAgICAgaWYoa2llcj09MCkga2llcj00OwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYocm96a2F6PT02OSkgamVtPXRydWU7CiAgICAgICAgICAgIGlmKGtpZXI9PTEpIGxlYisrOwogICAgICAgICAgICBlbHNlIGlmKGtpZXI9PTIpIGxlYj1sZWIrMTAwMDAwOwogICAgICAgICAgICBlbHNlIGlmKGtpZXI9PTMpIGxlYi0tOwogICAgICAgICAgICBlbHNlIGlmKGtpZXI9PTQpIGxlYj1sZWItMTAwMDAwOwogICAgICAgICAgICBpZihqZW0hPXRydWUpIGxpc3RhLnBvcF9iYWNrKCk7CiAgICAgICAgICAgIGVsc2UgamVtPWZhbHNlOwogICAgICAgICAgICB3YXo9bGlzdGEuc2l6ZSgpOwogICAgICAgICAgICBsaXN0YS5yZW1vdmUobGViKTsKICAgICAgICAgICAgY2hlY2s9bGlzdGEuc2l6ZSgpOwogICAgICAgICAgICBpZiAoY2hlY2srMTw9d2F6KQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBrdG9yYWRlYWQ9YjsKICAgICAgICAgICAgICAgIGI9bGVuZ3RoOwogICAgICAgICAgICAgICAgenlqZT1mYWxzZTsKICAgICAgICAgICAgfQogICAgICAgICAgICBsaXN0YS5wdXNoX2Zyb250KGxlYik7CiAgICAgICAgfQogICAgICAgIGlmICh6eWplPT10cnVlKSBjb3V0PDwiVEFLIjw8ZW5kbDsKICAgICAgICBlbHNlIGNvdXQ8PGt0b3JhZGVhZDw8ZW5kbDsKICAgICAgICBsaXN0YS5jbGVhcigpOwogICAgfQogICAgcmV0dXJuIDA7Cn0=
Ngo2IEZMRVJGRgo4IEVFRUVMTExMCjMzIEVMRUxFUkVMRUxFRVJFTEVMRVJFTEVMUkVMRUxFRUZFRQozMyBFTEVMRVJFTEVMRUVSRUxFTEVSRUxFTFJFTEVMRUVGRUYKNiBFRUVSUlIKMzAgRUVFRVJGRkZGUkZGUkZSRkZMRUxMRVJMTExSRlJGUg==
6
6 FLERFF
8 EEEELLLL
33 ELELERELELEERELELERELELRELELEEFEE
33 ELELERELELEERELELERELELRELELEEFEF
6 EEERRR
30 EEEERFFFFRFFRFRFFLELLERLLLRFRFR