Robert Floyd

Robert W Floyd was an American computer scientist and a Turing Award winner. In programming contests his best known result is the Floyd Warshall algorithm, which finds all pairs shortest paths and the transitive closure. The algorithm has many uses, and this problem is not one of them.

Stitches is the terror of Darkshire. He leaves a trail of putrid bile behind him, and walking on it slows you down by 35%. The bile does not disappear after he is killed. Two areas of the map are separated if there is no way to get from one to the other without stepping on bile.

Stitches walks a length of $1$ in one of the four directions (up, down, left, right) and then decides whether to turn. The map is a grid of $4098 \times 4098$ cells and Stitches walks along the edges of the cells. He starts at the exact center of the grid and walks a total length of at most $2048$, so he never touches the boundary of the grid.

As the mayor of Darkshire you want to know how many separated areas the map falls apart into. You could build a graph whose vertices are the cells, join two neighbouring cells whenever Stitches did not walk on the edge between them, run the Floyd Warshall algorithm to decide whether two cells lie in the same area, then count the areas with a disjoint set structure. The grid holds more than 16 million cells, so that method is far too slow. Find a faster one.

The first line holds the number of test cases $T$. ($1 \le T \le 30$)

Each test case is one line holding the sequence of Stitches' moves. U is up, D is down, L is left and R is right. The length of the sequence is between $1$ and $2048$.

For each test case, print the number of separated areas on its own line.