#include <iostream>
#include <list>
using namespace std;
long long n,length,leb,kier,kaput,waz,check,ktoradead,rozkaz;
bool jem,zyje;
list <long long> lista;
string data;
int main()
{
cin>>n;
while (n--)
{
cin>>length >> data;
lista.push_front(1000010000);
leb=1000010000;
kier=1,waz=1,zyje=true,ktoradead=0;
for(char rozkaz : data)
{
ktoradead++;
if(rozkaz==82)
{
kier++;
if(kier==5) kier=1;
}
else if(rozkaz==76)
{
kier--;
if(kier==0) kier=4;
}
else if(rozkaz!=69) lista.pop_back();
if(kier==1) leb++;
else if(kier==2) leb=leb+100000;
else if(kier==3) leb--;
else if(kier==4) leb=leb-100000;
waz=lista.size();
lista.remove(leb);
check=lista.size();
if (check+1<=waz)
{
zyje = false;
break;
}
lista.push_front(leb);
}
if (zyje==true) cout<<"TAK"<<'\n';
else cout<<ktoradead<<'\n';
lista.clear();
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bGlzdD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKbG9uZyBsb25nIG4sbGVuZ3RoLGxlYixraWVyLGthcHV0LHdheixjaGVjayxrdG9yYWRlYWQscm96a2F6Owpib29sIGplbSx6eWplOwpsaXN0IDxsb25nIGxvbmc+IGxpc3RhOwpzdHJpbmcgZGF0YTsKaW50IG1haW4oKQp7CiAgICBjaW4+Pm47CiAgICB3aGlsZSAobi0tKQogICAgewogICAgICAgIGNpbj4+bGVuZ3RoID4+IGRhdGE7CiAgICAgICAgbGlzdGEucHVzaF9mcm9udCgxMDAwMDEwMDAwKTsKICAgICAgICBsZWI9MTAwMDAxMDAwMDsKICAgICAgICBraWVyPTEsd2F6PTEsenlqZT10cnVlLGt0b3JhZGVhZD0wOwogICAgICAgIGZvcihjaGFyIHJvemtheiA6IGRhdGEpCiAgICAgICAgewogICAgICAgICAgICBrdG9yYWRlYWQrKzsKICAgICAgICAgICAgaWYocm96a2F6PT04MikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAga2llcisrOwogICAgICAgICAgICAgICAgaWYoa2llcj09NSkga2llcj0xOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYocm96a2F6PT03NikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAga2llci0tOwogICAgICAgICAgICAgICAgaWYoa2llcj09MCkga2llcj00OwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYocm96a2F6IT02OSkgbGlzdGEucG9wX2JhY2soKTsKICAgICAgICAgICAgaWYoa2llcj09MSkgbGViKys7CiAgICAgICAgICAgIGVsc2UgaWYoa2llcj09MikgbGViPWxlYisxMDAwMDA7CiAgICAgICAgICAgIGVsc2UgaWYoa2llcj09MykgbGViLS07CiAgICAgICAgICAgIGVsc2UgaWYoa2llcj09NCkgbGViPWxlYi0xMDAwMDA7CiAgICAgICAgICAgIHdhej1saXN0YS5zaXplKCk7CiAgICAgICAgICAgIGxpc3RhLnJlbW92ZShsZWIpOwogICAgICAgICAgICBjaGVjaz1saXN0YS5zaXplKCk7CiAgICAgICAgICAgIGlmIChjaGVjaysxPD13YXopCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHp5amUgPSBmYWxzZTsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGxpc3RhLnB1c2hfZnJvbnQobGViKTsKICAgICAgICB9CiAgICAgICAgaWYgKHp5amU9PXRydWUpIGNvdXQ8PCJUQUsiPDwnXG4nOwogICAgICAgIGVsc2UgY291dDw8a3RvcmFkZWFkPDwnXG4nOwogICAgICAgIGxpc3RhLmNsZWFyKCk7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=