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>
const long long maxn = 1e6 + 9, inf = 0x3f3f3f3f3f3f3f3f;
inline long long Read() {
  long long x(0), f(1);
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  return x * f;
}
long long T, n;
char s[maxn];
long long pre_i[2][maxn], pre_x[2][maxn], sum_i[2][maxn], sum_x[2][maxn];
struct node {
  long long x, y;
} a[maxn];
int main() {
  T = Read();
  while (T--) {
    scanf(" %s", s + 1);
    n = strlen(s + 1);
    a[0] = (node){0, 0};
    for (long long i = 1; i <= n; ++i) {
      a[i].x = a[i - 1].x;
      a[i].y = a[i - 1].y;
      if (s[i] == 'W') {
        a[i].x = a[i - 1].x + 1;
      }
      if (s[i] == 'S') {
        a[i].x = a[i - 1].x - 1;
      }
      if (s[i] == 'A') {
        a[i].y = a[i - 1].y - 1;
      }
      if (s[i] == 'D') {
        a[i].y = a[i - 1].y + 1;
      }
    }
    pre_i[0][0] = pre_i[1][0] = sum_i[0][n + 1] = sum_i[1][n + 1] = 0;
    pre_x[0][0] = pre_x[1][0] = sum_x[0][n + 1] = sum_x[1][n + 1] = 0;
    for (long long i = 1; i <= n; ++i) {
      pre_i[0][i] = std::min(pre_i[0][i - 1], a[i].x);
      pre_i[1][i] = std::min(pre_i[1][i - 1], a[i].y);
      pre_x[0][i] = std::max(pre_x[0][i - 1], a[i].x);
      pre_x[1][i] = std::max(pre_x[1][i - 1], a[i].y);
    }
    sum_i[0][n] = sum_x[0][n] = a[n].x;
    sum_i[1][n] = sum_x[1][n] = a[n].y;
    for (long long i = n - 1; i >= 0; --i) {
      sum_i[0][i] = std::min(sum_i[0][i + 1], a[i].x);
      sum_i[1][i] = std::min(sum_i[1][i + 1], a[i].y);
      sum_x[0][i] = std::max(sum_x[0][i + 1], a[i].x);
      sum_x[1][i] = std::max(sum_x[1][i + 1], a[i].y);
    }
    long long ret((pre_x[0][n] - pre_i[0][n] + 1) *
                  (pre_x[1][n] - pre_i[1][n] + 1));
    for (long long i = 1; i < n; ++i) {
      long long xi(inf), yi(inf), xx(-inf), yy(-inf);
      xi = pre_i[0][i];
      yi = pre_i[1][i];
      xx = pre_x[0][i];
      yy = pre_x[1][i];
      for (long long j = 1; j <= 4; ++j) {
        long long _xi(xi), _yi(yi), _xx(xx), _yy(yy);
        if (j == 1) {
          _xi = std::min(_xi, a[i].x + 1);
          _xx = std::max(_xx, a[i].x + 1);
          _xi = std::min(_xi, sum_i[0][i + 1] + 1);
          _yi = std::min(_yi, sum_i[1][i + 1]);
          _xx = std::max(_xx, sum_x[0][i + 1] + 1);
          _yy = std::max(_yy, sum_x[1][i + 1]);
        }
        if (j == 2) {
          _xi = std::min(_xi, a[i].x - 1);
          _xx = std::max(_xx, a[i].x - 1);
          _xi = std::min(_xi, sum_i[0][i + 1] - 1);
          _yi = std::min(_yi, sum_i[1][i + 1]);
          _xx = std::max(_xx, sum_x[0][i + 1] - 1);
          _yy = std::max(_yy, sum_x[1][i + 1]);
        }
        if (j == 3) {
          _yi = std::min(_yi, a[i].y - 1);
          _yy = std::max(_yy, a[i].y - 1);
          _yi = std::min(_yi, sum_i[1][i + 1] - 1);
          _xi = std::min(_xi, sum_i[0][i + 1]);
          _yy = std::max(_yy, sum_x[1][i + 1] - 1);
          _xx = std::max(_xx, sum_x[0][i + 1]);
        }
        if (j == 4) {
          _yi = std::min(_yi, a[i].y + 1);
          _yy = std::max(_yy, a[i].y + 1);
          _yi = std::min(_yi, sum_i[1][i + 1] + 1);
          _xi = std::min(_xi, sum_i[0][i + 1]);
          _yy = std::max(_yy, sum_x[1][i + 1] + 1);
          _xx = std::max(_xx, sum_x[0][i + 1]);
        }
        ret = std::min(ret, (_xx - _xi + 1) * (_yy - _yi + 1));
      }
    }
    std::cout << ret << std::endl;
  }
  return 0;
}
