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 java.io.*;
import java.util.*;

public class Codeforces
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int t=Integer.parseInt(bu.readLine());
        while(t-->0)
        {
            char s[]=bu.readLine().toCharArray();
            int n=s.length,i,c[][]=new int[n+1][6],u=0,v=0;
            for(i=1;i<=n;i++)
            {
                if(s[i-1]=='W') u++;
                else if(s[i-1]=='S') u--;
                else if(s[i-1]=='D') v++;
                else v--;
                c[i][0]=u;  //cur Y axis
                c[i][1]=v;  //cur X axis
                c[i][2]=Math.max(c[i-1][2],u);  //maximum reachable Y axis
                c[i][3]=Math.min(c[i-1][3],u);  //minimum reachable Y axis
                c[i][4]=Math.max(c[i-1][4],v);  //max X
                c[i][5]=Math.min(c[i-1][5],v);  //min X
            }

            int m[]=new int[4],d[][]={{0,1},{1,0},{0,-1},{-1,0}};
            long ans=Long.MAX_VALUE;
            for(i=n;i>=0;i--)
            {
                for(int di[]:d)
                ans=Math.min(ans,calculate(c[i],di,m));

                if(i>0)
                {
                    // note that maxima minima changes on the basis of addition of WASD to left
                    if(s[i-1]=='W') {m[0]++; m[1]++;}   //Y axis changes
                    else if(s[i-1]=='S') {m[0]--; m[1]--;}
                    else if(s[i-1]=='D') {m[2]++; m[3]++;}
                    else {m[2]--; m[3]--;}
                    m[0]=Math.max(m[0],0); m[1]=Math.min(m[1],0);
                    m[2]=Math.max(m[2],0); m[3]=Math.min(m[3],0);
                }
            }
            sb.append(ans+"\n");
        }
        System.out.print(sb);
    }

    static long calculate(int a[],int b[],int c[])
    {
        int tu=a[0]+b[0],tv=a[1]+b[1],d[]=new int[4];
        d[0]=Math.max(0,c[0]+tu); d[1]=Math.min(0,c[1]+tu);
        d[2]=Math.max(0,c[2]+tv); d[3]=Math.min(0,c[3]+tv); //these are our new coordinates to the right
        return 1l*(Math.max(a[2],d[0])-Math.min(a[3],d[1])+1)*(Math.max(a[4],d[2])-Math.min(a[5],d[3])+1);
        //max possible area[maxima-minima product]
    }
}
