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).
import sys; sys.setrecursionlimit(10**7)
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

def cvt(c):
    if c == 'W':
        return 0, 1
    elif c == 'S':
        return 0, -1
    elif c == 'A':
        return -1, 0
    elif c == 'D':
        return 1, 0

def solve(S):
    N = len(S)
    A = map(cvt, S)
    dp = [None] * N
    x=y=x1=x2=y1=y2=0
    for i in xrange(N-1, -1, -1):
        dx, dy = A[i]
        x -= dx
        y -= dy
        if x < x1: x1 = x
        if x > x2: x2 = x
        if y < y1: y1 = y
        if y > y2: y2 = y
        dp[i] = x1-x, x2-x, y1-y, y2-y

    ans = (x2-x1+1) * (y2-y1+1)
    x=y=x1=x2=y1=y2=0
    for i, (dx, dy) in enumerate(A):
        for nx, ny in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
            px1, px2, py1, py2 = dp[i]
            ax1 = min(x1, nx, x, nx + px1)
            ax2 = max(x2, nx, x, nx + px2)
            ay1 = min(y1, ny, y, ny + py1)
            ay2 = max(y2, ny, y, ny + py2)
            cand = (ax2 - ax1 + 1) * (ay2 - ay1 + 1)
            if cand < ans:
                ans = cand
                
        x += dx
        y += dy
        if x < x1: x1 = x
        if x > x2: x2 = x
        if y < y1: y1 = y
        if y > y2: y2 = y
        
    return ans

for _ in xrange(rri()):
    print solve(rr())
