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>
using namespace std;
const int N = 200010;
const int INF = 1e9;
int _w;
int n;
char str[N];
bool intersect(int l1, int r1, int l2, int r2) {
  int l = max(l1, l2);
  int r = min(r1, r2);
  return l <= r;
}
bool checkws(int up, int down) {
  int upmin = INF;
  int upmax = -1;
  int downmin = INF;
  int downmax = -1;
  int x = 0;
  if (x == up) {
    upmin = min(upmin, 0);
    upmax = max(upmax, 0);
  }
  if (x == down) {
    downmin = min(downmin, 0);
    downmax = max(downmax, 0);
  }
  for (int i = 1; i <= n; ++i) {
    if (str[i] == 'W') {
      ++x;
    } else if (str[i] == 'S') {
      --x;
    }
    if (x == up) {
      upmin = min(upmin, i);
      upmax = max(upmax, i);
    }
    if (x == down) {
      downmin = min(downmin, i);
      downmax = max(downmax, i);
    }
  }
  return intersect(upmin, upmax, downmin, downmax) ? false : true;
}
bool checkad(int lft, int rait) {
  int lftmin = INF;
  int lftmax = -1;
  int raitmin = INF;
  int raitmax = -1;
  int y = 0;
  if (y == lft) {
    lftmin = min(lftmin, 0);
    lftmax = max(lftmax, 0);
  }
  if (y == rait) {
    raitmin = min(raitmin, 0);
    raitmax = max(raitmax, 0);
  }
  for (int i = 1; i <= n; ++i) {
    if (str[i] == 'A') {
      --y;
    } else if (str[i] == 'D') {
      ++y;
    }
    if (y == lft) {
      lftmin = min(lftmin, i);
      lftmax = max(lftmax, i);
    }
    if (y == rait) {
      raitmin = min(raitmin, i);
      raitmax = max(raitmax, i);
    }
  }
  return intersect(lftmin, lftmax, raitmin, raitmax) ? false : true;
}
void solve() {
  int x = 0, y = 0;
  int up = 0, down = 0, lft = 0, rait = 0;
  for (int i = 1; i <= n; ++i)
    if (str[i] == 'W') {
      ++x;
      up = max(up, x);
    } else if (str[i] == 'S') {
      --x;
      down = min(down, x);
    } else if (str[i] == 'A') {
      --y;
      lft = min(lft, y);
    } else {
      assert(str[i] == 'D');
      ++y;
      rait = max(rait, y);
    }
  int dx = up - down + 1;
  int dy = rait - lft + 1;
  long long ans = 1LL * dx * dy;
  if (dx >= 3 && checkws(up, down)) ans = min(ans, 1LL * (dx - 1) * dy);
  if (dy >= 3 && checkad(lft, rait)) ans = min(ans, 1LL * (dy - 1) * dx);
  cout << ans << endl;
}
int main() {
  int T;
  _w = scanf("%d", &T);
  while (T--) {
    _w = scanf("%s", str + 1);
    n = (int)strlen(str + 1);
    solve();
  }
  return 0;
}
