격자 낙서

길고 지루한 주간 회의 중에, 한 교수님이 수첩에 인쇄된 격자 위에 낙서를 시작했다. 교수님은 격자의 경계선 위에 있는 격자점 $P$ 에서 출발한다(따라서 $P$ 는 한 개 또는 두 개 격자 칸의 꼭짓점이다). 그 칸들 중 하나의 대각선을 그린 뒤, 45° 방향의 직선을 따라 격자의 다른 변 위의 점 $Q$ 에 닿을 때까지 계속 긋는다. 이어서 $Q$ 에서 선분 $PQ$ 에 수직인 새 선을 또 다른 변에 닿을 때까지 긋는다. 이렇게 바로 앞 선분에 수직인 선을 계속 추가하다가, 더 이상 새 선을 그을 수 없으면 멈춘다 — 수직선이 어떤 칸의 대각선으로 시작할 수 없거나, 이미 그은 선 위에 겹쳐지는 경우이다. 그 순간 교수님은 자신이 그린 그림이 격자를 몇 개의 최소 직사각형으로 나누었는지 궁금해졌다.

격자의 크기 $R$ 과 $C$, 경계 위 시작점 $P$ 의 좌표, 그리고 첫 선의 방향이 주어질 때, 만들어지는 최소 직사각형의 개수를 구하는 프로그램을 작성하라.

첫 줄에 테스트 케이스의 수 $t$ 가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다.

첫 줄에는 두 정수 $R$ 과 $C$ 가 주어진다. 각각 가로 격자선과 세로 격자선의 개수이다($2 \le R, C \le 1000$).

둘째 줄에는 시작점 $P$ 의 좌표를 나타내는 두 정수 $y$ 와 $x$ 가 주어진다($1 \le y \le R$, $1 \le x \le C$). 격자의 왼쪽 위 점이 $x = y = 1$ 이며, $x$ 는 오른쪽으로, $y$ 는 아래쪽으로 증가한다. $P$ 는 항상 격자의 변 위에 있다.

셋째 줄에는 첫 선의 방향을 나타내는 두 글자 코드가 주어진다.

• DR — 첫 이동은 오른쪽 아래 방향
• DL — 첫 이동은 왼쪽 아래 방향
• UL — 첫 이동은 왼쪽 위 방향
• UR — 첫 이동은 오른쪽 위 방향

각 테스트 케이스마다, 만들어지는 서로 겹치지 않는 최소 직사각형의 개수를 한 줄에 출력한다.