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

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Oops, It's Yesterday Thrice More!time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$$$.

Output

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.

ExampleInput
4
1
L
3
LDL
8
RLDULULU
4
LRUD
Output
2
6
16
4
Note

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

加入题单

上一题 下一题 算法标签: