409602: GYM103643 E Oops, It's Yesterday Thrice More!

Misaka had an $$$n$$$ by $$$m$$$ grid of kangaroos. She also had a string $$$s$$$ of instructions which were all L, R, D, or U.

If the current instruction was L, a kangaroo on spot $$$x, y$$$ would move to $$$\max(1, x-1), y$$$

If the current instruction was R, a kangaroo on spot $$$x, y$$$ would move to $$$\min(n, x+1), y$$$

If the current instruction was D, a kangaroo on spot $$$x, y$$$ would move to $$$x, \max(1, y-1)$$$

If the current instruction was U, a kangaroo on spot $$$x, y$$$ would move to $$$x, \min(m, y+1)$$$

A given instruction will be followed by all kangaroos on the board. If two kangaroos end up on the same spot, they will move together for all of the following instructions.

Initially there is a kangaroo on every cell $$$x, y$$$ such that $$$(1 \leq x \leq n), (1, \leq y, \leq m)$$$. After the instruction string $$$s$$$ was executed, every kangaroo was gathered on the same cell.

Unfortunately, Misaka has forgotted the original size of the grid $$$n$$$ and $$$m$$$! Luckily, she still remembers the instruction string $$$s$$$ and would like you to find the maximum area of the original grid.

The first line will be one integer $$$T$$$ denoting the number of testcases $$$(1 \leq T \leq 100)$$$. Each of the following $$$T$$$ lines will contain an integer $$$n$$$ denoting the length of the instruction string followed by a string $$$s$$$ denoted the instruction string $$$(1 \leq n \leq 10^6)$$$. It is guaranteed that the sum of $$$n$$$ over all testcases is less than $$$10^6$$$.

You will output $$$T$$$ lines. Each line will contain one integer denoting the maximum area of a grid that guarantees after the instruction string $$$s$$$ is executed all the kangaroos are on the same spot.

4
1
L
3
LDL
8
RLDULULU
4
LRUD

2
6
16
4

In the first sample, the kangaroos on (1, 1) will all move to (1, 2) on a 1x2 board. It can be proven no better area exists.

$$$---------------------------------------------$$$

Problem idea: 3366

Problem preparation: 3366

Occurrences: Novice 5, Intermediate 2