무작위 산책

야시(Jaś)는 이른바 무작위 산책을 해 보기로 했다. 그가 사는 고장의 길은 정사각형 격자 모양으로 놓여 있어, $100$미터마다 교차로가 나오고 그곳에서 직진하거나 왼쪽 또는 오른쪽으로 꺾을 수 있다. 왔던 방향으로 되돌아갈 수도 있다. 어떤 길을 택하든 다시 $100$미터를 가면 똑같은 선택을 마주하게 된다.

야시는 집에서 출발해 교차로에 이를 때마다 이 중 하나를 골라 이동했고, 그 선택을 모두 순서대로 기록해 두었다. 몇 시간을 걷던 중 하늘에 먹구름이 몰려와 곧 폭풍이 닥칠 듯했다. 그는 서둘러 길을 벗어나 주변의 들판과 숲을 가로질러 집으로 돌아가야 한다.

이때 야시는 궁금해졌다. 지금까지 걸어온 자취(지나온 길)를 어느 지점에서도 가로지르지 않는 경로로 집까지 돌아갈 수 있을까? 돌아가는 경로가 반드시 정식 길만 따를 필요는 없고, 주변 들판과 숲을 지나는 임의의 이동이어도 된다. 집에 도착하는 것은 그가 산책에서 가장 처음 방문한 교차로에 도달하는 것과 같다고 본다.

각 기록에 대해 그런 경로가 존재하는지 판정하여라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다. 이어지는 $T$개의 줄에 각각 하나의 테스트 케이스가 주어진다. 각 줄은 야시가 폭풍이 오기 전까지 내린 선택의 수 $n$ ($1 \le n \le 10^5$)으로 시작하고, 그 뒤에 $n$개의 선택이 순서대로 문자로 주어진다.

• P : 직진했다.
• L : 왼쪽으로 꺾었다.
• R : 오른쪽으로 꺾었다.
• C : 왔던 방향으로 되돌아갔다.

각 테스트 케이스마다 한 줄씩 출력한다. 지금까지 걸어온 자취를 가로지르지 않는 경로로 집에 돌아갈 수 있으면 TAK을, 그렇지 않으면 NIE를 출력한다. 집에 도착하는 것은 가장 처음 방문한 교차로에 도달하는 것과 같다.