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

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.

输入描述:

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×), indicating the sequence of the robot commands.
It's guaranteed that the total length of s over all test cases will not exceed 5×.

输出描述:

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.

3
DSAWWAW
D
WA

8
2
4

备注:

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.