Griddy Hobby

During a long, dull weekly meeting, a professor started doodling on the grid printed in his notebook. He begins at a grid point $P$ that lies on the boundary of the grid (so $P$ is a corner of one or two grid cells). He draws the diagonal of one of those cells and keeps going in a straight line at 45° until he reaches a point $Q$ on another edge of the grid. From $Q$ he draws a new line perpendicular to $PQ$, continuing until it hits yet another edge. He keeps adding lines this way, each perpendicular to the previous one, until he can no longer draw a new line — either because a perpendicular line would not begin with the diagonal of a cell, or because it would land on a line he has already drawn. At that moment he wonders how many minimal rectangles his drawing has carved out of the grid.

Given the grid dimensions $R$ and $C$, the coordinates of the starting point $P$ on the boundary, and the direction of the first line, write a program that reports the number of minimal rectangles.

The first line contains an integer $t$, the number of test cases. Each test case is described by three lines.

The first line contains two integers $R$ and $C$ — the number of horizontal and vertical gridlines, respectively ($2 \le R, C \le 1000$).

The second line contains two integers $y$ and $x$ — the coordinates of the starting point $P$ ($1 \le y \le R$, $1 \le x \le C$). The upper-left grid point is $x = y = 1$, with $x$ increasing to the right and $y$ increasing downward. $P$ always lies on an edge of the grid.

The third line contains a two-letter direction code for the first line:

• DR — the first move goes down and to the right,
• DL — the first move goes down and to the left,
• UL — the first move goes up and to the left,
• UR — the first move goes up and to the right.

For each test case, print a single line containing the number of minimal (non-overlapping) rectangles formed.