PROGRAMMING:Robotics Innovation Lab
Ku Ku Ku Ki Ki, Ku Ku Ku Ki Ki, the robot is coming!
Little Gyro has a mechanical robot in his experimental lab, which is currently placed in some cell of a rectangular grid. Now given a string $$s$$——a sequence of commands for his program to control the robot. It can perform four commands:
* 'W' —— The robot will move one cell up;
* 'S' —— The robot will move one cell down;
* 'A' —— The robot will move one cell left;
* 'D' —— The robot will move one cell right.
Because the area of the Robotic Innovation Lab in our school is limited, Little Gyro is asked to find the minimum possible area of such a grid that existing an initial position where Little Gyro can place the robot, and the robot will not get out of the grid while running the sequence of the commands $$s$$. For example, if $$s$$="DSAWWAW" and then the minimum grid is the $$4$$ ×$$ 3$$ grid:
1. First, Little Gyro can place the robot in the cell (3, 2) initially;
2. Then, the robot performs the command 'D' and moves to (3, 3);
3. The robot performs the command 'S' and moves to (4, 3) later on;
4. After that, the robot performs the command 'A' and moves to (4, 2);
5. Next, the robot performs the command 'W' and moves to (3, 2);
6. The robot performs the command 'W' and moves to (2, 2) afterwards;
7. And the robot performs the command 'A' and moves to (2, 1) in the following step;
8. Finally, the robot performs the command 'W' and moves to (1, 1).
![ Question surface diagram. PNG] (~ / 57be4388-fb8f-4e83-ae33-e234fa1ee1c. PNG)
In order to avoid the robot beyond control, fortunately, Little Gyro is given 4 extra letters to adjust the position of the robot: one 'W', one 'A', one 'S', and one 'D'. Little Gyro must insert one of these letters in any position of sequence $$s$$ to minimize the area of grid. Please note that, for all the directions Little Gyro just has the extra chance once only.
Now given the sequence $$s$$ of commands for the robot controlling program, please help Little Gyro find the minimum area of the grid that you can achieve.
### Input Specification:
There are multiple test cases. The first line of the input contains an integer $$T$$ (1 ≤ $$T$$ ≤ 1000), indicating the number of test cases. For each test case:
Each line contains a single string $$s$$ (1 ≤ $$|s|$$ ≤ 2 ×$$ 10^5$$), indicating the sequence of the robot commands.
It's guaranteed that the total length of $$s$$ over all test cases will not exceed 5 ×$$ 10^5$$.
### Output Specification:
For each test case, output the minimum area of the grid so that the robot will not move out of it under all the commands.
### Sample Input:
```in
three
DSAWWAW
D
WA
```
### Sample Output:
```out
eight
two
four
```
### Hint:
For the first sample, Little Gyro can insert a character 'D' between the fifth step and the sixth step in order to minimum the area, and the minimum area of the grid is 2 × 4 = 8, so the answer is 8.
answer：If there is no answer, please comment
At first thought, it's easy to record the longest distance that can be reached up and down left and right, calculate the length len and width Wei, and consider ans = len × The value of Wei, when len is large, makes Wei minus one, ans minus more, otherwise makes len minus one. However, there are conditions to limit whether it can be reduced, because if you move one space to the right before reaching the left maximum, it can reduce the left maximum, but it may increase the right maximum after reaching the left maximum. Therefore, you need to record the time of the first arrival and the last arrival to determine whether it can be reduced by one.
Little Gyro has a mechanical robot in his experimental lab, which is currently placed in some cell of a rectangular grid. Now given a string $$s$$——a sequence of commands for his program to control the robot. It can perform four commands:
* 'W' —— The robot will move one cell up;
* 'S' —— The robot will move one cell down;
* 'A' —— The robot will move one cell left;
* 'D' —— The robot will move one cell right.
Because the area of the Robotic Innovation Lab in our school is limited, Little Gyro is asked to find the minimum possible area of such a grid that existing an initial position where Little Gyro can place the robot, and the robot will not get out of the grid while running the sequence of the commands $$s$$. For example, if $$s$$="DSAWWAW" and then the minimum grid is the $$4$$ ×$$ 3$$ grid:
1. First, Little Gyro can place the robot in the cell (3, 2) initially;
2. Then, the robot performs the command 'D' and moves to (3, 3);
3. The robot performs the command 'S' and moves to (4, 3) later on;
4. After that, the robot performs the command 'A' and moves to (4, 2);
5. Next, the robot performs the command 'W' and moves to (3, 2);
6. The robot performs the command 'W' and moves to (2, 2) afterwards;
7. And the robot performs the command 'A' and moves to (2, 1) in the following step;
8. Finally, the robot performs the command 'W' and moves to (1, 1).
![ Question surface diagram. PNG] (~ / 57be4388-fb8f-4e83-ae33-e234fa1ee1c. PNG)
In order to avoid the robot beyond control, fortunately, Little Gyro is given 4 extra letters to adjust the position of the robot: one 'W', one 'A', one 'S', and one 'D'. Little Gyro must insert one of these letters in any position of sequence $$s$$ to minimize the area of grid. Please note that, for all the directions Little Gyro just has the extra chance once only.
Now given the sequence $$s$$ of commands for the robot controlling program, please help Little Gyro find the minimum area of the grid that you can achieve.
### Input Specification:
There are multiple test cases. The first line of the input contains an integer $$T$$ (1 ≤ $$T$$ ≤ 1000), indicating the number of test cases. For each test case:
Each line contains a single string $$s$$ (1 ≤ $$|s|$$ ≤ 2 ×$$ 10^5$$), indicating the sequence of the robot commands.
It's guaranteed that the total length of $$s$$ over all test cases will not exceed 5 ×$$ 10^5$$.
### Output Specification:
For each test case, output the minimum area of the grid so that the robot will not move out of it under all the commands.
### Sample Input:
```in
three
DSAWWAW
D
WA
```
### Sample Output:
```out
eight
two
four
```
### Hint:
For the first sample, Little Gyro can insert a character 'D' between the fifth step and the sixth step in order to minimum the area, and the minimum area of the grid is 2 × 4 = 8, so the answer is 8.
answer：If there is no answer, please comment
At first thought, it's easy to record the longest distance that can be reached up and down left and right, calculate the length len and width Wei, and consider ans = len × The value of Wei, when len is large, makes Wei minus one, ans minus more, otherwise makes len minus one. However, there are conditions to limit whether it can be reduced, because if you move one space to the right before reaching the left maximum, it can reduce the left maximum, but it may increase the right maximum after reaching the left maximum. Therefore, you need to record the time of the first arrival and the last arrival to determine whether it can be reduced by one.