Robert Floyd

Robert W Floyd는 튜링상을 받은 미국의 컴퓨터 과학자다. 프로그래밍 대회에서 가장 많이 쓰이는 그의 업적은 모든 쌍 최단 경로와 이행 폐포를 구하는 Floyd Warshall 알고리즘이다. 쓸모가 많은 알고리즘이지만 이 문제는 그 쓸모에 들어가지 않는다.

Stitches는 Darkshire의 골칫거리다. 그가 지나간 자리에는 악취가 나는 담즙이 남고, 그 위를 밟으면 이동 속도가 35% 느려진다. 담즙은 Stitches가 쓰러진 뒤에도 사라지지 않는다. 담즙을 밟지 않고는 한쪽에서 다른 쪽으로 갈 수 없으면 두 구역은 서로 분리된 것이다.

Stitches는 상하좌우 중 한 방향으로 길이 $1$만큼 걷고 나서 방향을 바꿀지 정한다. 지도는 $4098 \times 4098$개의 칸으로 이루어진 격자이고, Stitches는 칸의 변을 따라 걷는다. 출발 지점은 격자의 정중앙이며 걷는 거리가 최대 $2048$이라 격자의 경계에는 결코 닿지 않는다.

Darkshire의 시장인 당신은 Stitches가 걷고 난 뒤 지도가 몇 개의 구역으로 나뉘는지 알고 싶다. 칸을 정점으로 두고 Stitches가 밟지 않은 변으로 이웃한 칸끼리 이어 그래프를 만든 다음, Floyd Warshall 알고리즘으로 두 칸이 같은 구역에 있는지 판정하고 서로소 집합 자료구조로 구역의 수를 셀 수 있다. 그러나 격자의 칸이 1600만 개를 넘어서 이 방법은 너무 느리다. 더 빠른 방법을 찾아라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 30$)

각 테스트 케이스는 한 줄로 이루어지며, Stitches가 움직인 순서를 나타내는 문자열이 주어진다. U는 위, D는 아래, L은 왼쪽, R은 오른쪽을 뜻한다. 문자열의 길이는 $1$ 이상 $2048$ 이하다.

각 테스트 케이스마다 분리된 구역의 수를 한 줄에 출력한다.