판도라

한국천문연구협회(KARA)가 발사한 무인 로봇 판도라가 화성에 도착해, 경계선이 단순 직교 다각형(simple rectilinear polygon)인 구조물을 발견했다.

직교 다각형은 모든 변이 수평 또는 수직인 다각형으로, 각 꼭짓점의 내각은 90° 또는 270°이다. 이러한 다각형이 (1) 모든 꼭짓점에서 정확히 두 변이 만나고 (2) 두 변이 서로의 끝점에서만 만날 때, 그 다각형을 단순(simple)하다고 한다.

판도라는 경계선의 모양을 알아내기 위해 시작점으로 돌아올 때까지 경계선을 반시계 방향으로 따라 걸으며, 각 꼭짓점에서의 회전 방향만을 보고했다. 문자 L은 왼쪽 회전(내각 90°)을, 문자 R은 오른쪽 회전(내각 270°)을 뜻한다. 전송 과정에서 변의 길이 정보는 사라졌으므로, 회전 순서만으로 모양을 파악해야 한다.

이 보고는 문자 L과 R로 이루어진 문자열 $S$이다. 예를 들어 LLLL은 축에 평행한 직사각형을 나타낸다. $S$에 들어 있는 L의 개수를 $l$, R의 개수를 $r$라 하자. 경로가 반시계 방향이므로 항상 $l = r + 4$이며, $l \ge 4$이고 $r \ge 0$이다. 반대로, $l = r + 4$를 만족하는 모든 문자열 $S$에 대해, 반시계 방향 회전 순서가 정확히 $S$가 되는 $l + r$개의 꼭짓점을 가진 단순 직교 다각형을 하나 이상 그릴 수 있다.

단순 직교 다각형이 X축에 대해 단조(monotone)라는 것은, X축에 수직인 모든 직선(즉 모든 수직선)이 그 다각형과 많아야 하나의 연결된 선분에서 만난다는 뜻이다. Y축에 대한 단조성은 수평선을 사용해 같은 방식으로 정의한다. 주어진 $S$로 그릴 수 있는 모든 단순 직교 다각형은 같은 단조성을 가지므로, 이들이 단조인 축의 개수는 오직 $S$에만 의존한다. 그 축의 개수를 출력하라. 어느 축에 대해서도 단조가 아니면 0, 정확히 한 축에 대해 단조이면 1, 두 축 모두에 대해 단조이면 2이다.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 문자 L과 R로 이루어진 문자열 $S$가 하나씩 주어지며, L의 개수는 R의 개수보다 정확히 4개 많다. $S$의 길이는 4 이상 100000 이하이다.

각 테스트 케이스마다, $S$로 나타나는 단순 직교 다각형이 단조인 축의 개수(0, 1, 또는 2)를 한 줄에 출력한다.