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).
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Bilongboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1202C
   {
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         int[][] pos = new int[200003][2];
         int[][] prefmin = new int[200003][2];
         int[][] prefmax = new int[200003][2];
         int[][] sufmin = new int[200003][2];
         int[][] sufmax = new int[200003][2];
         while(T-->0)
         {
            char[] arr = infile.readLine().toCharArray();
            int N = arr.length;
            int x = 0, y = 0;
              int mx = 0, my = 0, Mx = 0, My = 0;
              int n = arr.length;
              prefmin[0][0] = prefmin[0][1] = prefmax[0][0] = prefmax[0][1] = 0;
              pos[0][0] = pos[0][1] = 0;
              for(int i = 0; i < n; i++) 
              {
                  x += equate(arr[i], 'D')-equate(arr[i], 'A');
                  y += equate(arr[i], 'W')-equate(arr[i], 'S');
                  pos[i + 1][0] = x;
                  pos[i + 1][1] = y;
                  prefmin[i + 1][0] = mx = Math.min(mx, x);
                  prefmin[i + 1][1] = my = Math.min(my, y);
                  prefmax[i + 1][0] = Mx = Math.max(Mx, x);
                  prefmax[i + 1][1] = My = Math.max(My, y);
              }
              long res = ((long) (Mx - mx + 1)) * ((long) (My - my + 1));
              mx = Mx = x; my = My = y;
              for(int i = n; i >= 0; i--) {
                  sufmin[i][0] = mx = Math.min(mx, pos[i][0]);
                  sufmin[i][1] = my = Math.min(my, pos[i][1]);
                  sufmax[i][0] = Mx = Math.max(Mx, pos[i][0]);
                  sufmax[i][1] = My = Math.max(My, pos[i][1]);
              }
              for(int i = 1; i < n; i++) {
                  res = Math.min(res, ((long) Math.max(prefmax[i][0], sufmax[i][0] - 1) - Math.min(prefmin[i][0], sufmin[i][0] - 1) + 1) * ((long) My - my + 1));
                  res = Math.min(res, ((long) Math.max(prefmax[i][0], sufmax[i][0] + 1) - Math.min(prefmin[i][0], sufmin[i][0] + 1) + 1) * ((long) My - my + 1));
                  res = Math.min(res, ((long) Mx - mx + 1) * ((long)Math.max(prefmax[i][1], sufmax[i][1] - 1) - Math.min(prefmin[i][1], sufmin[i][1] - 1) + 1));
                  res = Math.min(res, ((long) Mx - mx + 1) * ((long) Math.max(prefmax[i][1], sufmax[i][1] + 1) - Math.min(prefmin[i][1], sufmin[i][1] + 1) + 1));
              }
            sb.append(res+"\n");
         }
         System.out.print(sb);
      }
      public static int equate(char c, char letter)
      {
         if(c == letter)
            return 1;
         return 0;
      }
   }