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).
#include <bits/stdc++.h>
int Max(int* a, int b, int* l_p, int* f_p, int j) {
  if (b == *a) {
    *a = b;
    *l_p = j;
  } else if (b > *a) {
    *a = b;
    *l_p = j;
    *f_p = j;
  }
  return 0;
}
int Min(int* a, int b, int* l_p, int* f_p, int j) {
  if (b == *a) {
    *a = b;
    *l_p = j;
  } else if (b < *a) {
    *a = b;
    *l_p = j;
    *f_p = j;
  }
  return 0;
}
long long min(long long a, long long b) { return a < b ? a : b; }
int main() {
  int T;
  scanf("%d", &T);
  for (int i = 0; i < T; i++) {
    char move[200005];
    scanf("%s", move);
    int init_v = 0, init_h = 0;
    int min_x = 0, min_y = 0, max_x = 0, max_y = 0;
    int l_min_x = 0, l_max_x = 0, l_min_y = 0, l_max_y = 0;
    int f_min_x = 0, f_max_x = 0, f_min_y = 0, f_max_y = 0;
    for (int j = 0; j < strlen(move); j++) {
      if (move[j] == 'W') {
        init_v++;
        Max(&max_y, init_v, &l_max_y, &f_max_y, j);
      } else if (move[j] == 'S') {
        init_v--;
        Min(&min_y, init_v, &l_min_y, &f_min_y, j);
      } else if (move[j] == 'A') {
        init_h--;
        Min(&min_x, init_h, &l_min_x, &f_min_x, j);
      } else if (move[j] == 'D') {
        init_h++;
        Max(&max_x, init_h, &l_max_x, &f_max_x, j);
      }
    }
    int x_l = (max_x - min_x + 1);
    int y_l = (max_y - min_y + 1);
    int m_y_l = y_l;
    int m_x_l = x_l;
    if (l_min_x < f_max_x && (max_x - min_x) >= 2) {
      m_x_l--;
    }
    if (l_max_x < f_min_x && (max_x - min_x) >= 2) {
      m_x_l--;
    }
    if (l_min_y < f_max_y && (max_y - min_y) >= 2) {
      m_y_l--;
    }
    if (l_max_y < f_min_y && (max_y - min_y) >= 2) {
      m_y_l--;
    }
    long long ans = min((long long)(x_l) * (long long)m_y_l,
                        (long long)m_x_l * (long long)y_l);
    printf("%lld\n", ans);
  }
  return 0;
}
