You have a string s — a sequence of commands for your toy robot. The robot is placed in some cell of a rectangular grid. He can perform four commands:

  * 'W' — move one cell up; 
  * 'S' — move one cell down; 
  * 'A' — move one cell left; 
  * 'D' — move one cell right. 



Let Grid(s) be the grid of minimum possible area such that there is a position in the grid where you can place the robot in such a way that it will not fall from the grid while running the sequence of commands s. For example, if s = DSAWWAW then Grid(s) is the 4 × 3 grid:

  1. you can place the robot in the cell (3, 2); 
  2. the robot performs the command 'D' and moves to (3, 3); 
  3. the robot performs the command 'S' and moves to (4, 3); 
  4. the robot performs the command 'A' and moves to (4, 2); 
  5. the robot performs the command 'W' and moves to (3, 2); 
  6. the robot performs the command 'W' and moves to (2, 2); 
  7. the robot performs the command 'A' and moves to (2, 1); 
  8. the robot performs the command 'W' and moves to (1, 1). 

<image>

You have 4 extra letters: one 'W', one 'A', one 'S', one 'D'. You'd like to insert at most one of these letters in any position of sequence s to minimize the area of Grid(s).

What is the minimum area of Grid(s) you can achieve?

Input

The first line contains one integer T (1 ≤ T ≤ 1000) — the number of queries.

Next T lines contain queries: one per line. This line contains single string s (1 ≤ |s| ≤ 2 ⋅ 10^5, s_i ∈ \{W, A, S, D\}) — the sequence of commands.

It's guaranteed that the total length of s over all queries doesn't exceed 2 ⋅ 10^5.

Output

Print T integers: one per query. For each query print the minimum area of Grid(s) you can achieve.

Example

Input


3
DSAWWAW
D
WA


Output


8
2
4

Note

In the first query you have to get string DSAWW\underline{D}AW.

In second and third queries you can not decrease the area of Grid(s).
def Grid(S):
    xmin = [0, [-1]]
    xmax = [0, [-1]]
    ymin = [0, [-1]]
    ymax = [0, [-1]]
    y_s = 0
    x_s = 0
    n = len(S)
    for i in range(n):
        c = S[i]
        if c=='W':
            y_s+=1
        elif c=='S':
            y_s-=1
        elif c=='A':
            x_s-=1
        else:
            x_s+=1
        if x_s==xmin[0]:
            xmin[1].append(i)
        elif x_s < xmin[0]:
            xmin = [x_s, [i]]
            
        if x_s==xmax[0]:
            xmax[1].append(i)
        elif x_s > xmax[0]:
            xmax = [x_s, [i]]
        if y_s==ymin[0]:
            ymin[1].append(i)
        elif y_s < ymin[0]:
            ymin = [y_s, [i]]
            
        if y_s==ymax[0]:
            ymax[1].append(i)
        elif y_s > ymax[0]:
            ymax = [y_s, [i]]
    return [xmin, xmax, ymin, ymax]

def process(S):
    A, B, C, D = Grid(S)
    a, al = A
    b, bl = B
    c, cl = C
    d, dl = D
    answer = (b-a+1)*(d-c+1)
    if bl[-1] < al[0]-1 or al[-1] < bl[0]-1:
        answer = min(answer, (b-a)*(d-c+1))
    if dl[-1] < cl[0]-1 or cl[-1] < dl[0]-1:
        answer = min(answer, (b-a+1)*(d-c))
    return answer

t = int(input())
for i in range(t):
    S =  input()
    print(process(S))