Pandora

An unmanned robot named Pandora, launched by KARA (the Korea Astronomy Research Association), has landed on Mars, where it found a structure whose outline is a simple rectilinear polygon.

A rectilinear polygon is a polygon in which every edge is horizontal or vertical, so the interior angle at each vertex is either 90° or 270°. Such a polygon is simple when (1) exactly two edges meet at every vertex and (2) no two edges intersect except at a shared endpoint.

To recover the outline, Pandora walked along the boundary in counterclockwise order until it returned to the starting point, and reported, for each vertex, only the turning direction. The letter L marks a left turn (an interior angle of 90°) and the letter R marks a right turn (an interior angle of 270°). The edge lengths were lost in transmission, so the shape must be understood from the turn sequence alone.

The report is a string $S$ of the letters L and R. For instance, LLLL describes an axis-aligned rectangle. Let $l$ be the number of L's and $r$ the number of R's in $S$. Because the walk is counterclockwise, $l = r + 4$ always holds, with $l \ge 4$ and $r \ge 0$. Conversely, every string $S$ with $l = r + 4$ can be realized by one or more simple rectilinear polygons on $l + r$ vertices whose counterclockwise turn sequence is exactly $S$.

A simple rectilinear polygon is monotone with respect to the X-axis if every line perpendicular to the X-axis (that is, every vertical line) meets the polygon in at most one connected segment. Monotonicity with respect to the Y-axis is defined the same way using horizontal lines. All simple rectilinear polygons realizing a given $S$ share the same monotonicity, so the number of axes they are monotone with respect to depends only on $S$. Output that number: 0 if they are monotone to neither axis, 1 if to exactly one axis, and 2 if to both axes.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one string $S$ consisting of the letters L and R, where the number of L's is exactly four more than the number of R's. The length of $S$ is between 4 and 100000 inclusive.

For each test case, print one line containing the number of axes (0, 1, or 2) that the simple rectilinear polygons described by $S$ are monotone with respect to.