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).
from sys import stdin
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())


t = int(input())

while t:
    s = str(rd().strip())
    s = '0' + s + '0'
    g = s[::-1]

    posx = [0] *len(s)
    posy = [0] *len(s)
    l = [0] *len(s)
    r = [0] *len(s)
    tp = [0] *len(s)
    b = [0] * len(s)

    rposx = [0] * len(s)
    rposy = [0] * len(s)
    rl = [0] * len(s)
    rr = [0] * len(s)
    rt = [0] * len(s)
    rb = [0] * len(s)


    posx[0] = posy[0] = l[0] = r[0] = tp[0] = b[0]  = 2*10**5+50

    for i in range(1,len(s)-1):
        if s[i] == 'W':
            posy[i] = posy[i-1] + 1

        elif s[i] == 'S':
            posy[i] = posy[i-1] - 1

        elif s[i] == 'A':
            posx[i] = posx[i-1] - 1

        elif s[i] == 'D':
            posx[i] = posx[i-1] + 1

        if not posx[i]:
            posx[i] = posx[i-1]
        if not posy[i]:
            posy[i] = posy[i-1]

        l[i] = min(l[i-1], posx[i])
        r[i] = max(r[i-1], posx[i])
        b[i] = min(b[i - 1], posy[i])
        tp[i] = max(tp[i - 1], posy[i])


    rt[0] = rb[0] = rposy[0] = posy[len(s) - 2]
    rl[0] = rr[0] = rposx[0] = posx[len(s) - 2]



    for i in range(1, len(g) -1):
        if g[i] == 'W':
            rposy[i] = rposy[i - 1] - 1

        elif g[i] == 'S':
            rposy[i] = rposy[i - 1] + 1

        elif g[i] == 'A':
            rposx[i] = rposx[i-1] + 1

        elif g[i] == 'D':
            rposx[i] = rposx[i-1] - 1

        if not rposx[i]:
            rposx[i] = rposx[i - 1]
        if not rposy[i]:
            rposy[i] = rposy[i - 1]

        rl[i] = min(rl[i-1], rposx[i])
        rr[i] = max(rr[i-1], rposx[i])
        rb[i] = min(rb[i - 1], rposy[i])
        rt[i] = max(rt[i - 1], rposy[i])

    dx = False
    dy = False
    ls = len(s) - 2


    for i in range (1,len(s)-1):

        if (l[i] - rl[ls-i])*(r[i] - rr[ls-i]) > 0:
            dx = True
        if (tp[i] - rt[ls-i])*(b[i] - rb[ls-i]) > 0:
            dy = True


    wd = r[ls]-l[ls] + 1
    ht = tp[ls] - b[ls] +1

    ans = wd*ht

    if dx:
        ans = min(ans,(wd-1)*ht)
    if dy:
        ans = min(ans,(ht-1)*wd)

    print(ans)

    t -= 1
