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;
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long a, long long b, long long m) {
  if (b == 0LL) return 1LL;
  if (b == 1LL) return mod(a, m);
  long long k = mod(exp(a, b / 2, m), m);
  if (b & 1LL) {
    return mod(a * mod(k * k, m), m);
  } else
    return mod(k * k, m);
}
struct node {
  int mx, tot, pre, suf;
  node() { mx = tot = pre = suf = 0; }
  node operator+(const node &o) const {
    node res;
    res.tot = tot + o.tot;
    res.pre = max(pre, tot + o.pre);
    res.suf = max(o.suf, o.tot + suf);
    res.mx = max(mx, o.mx);
    res.mx = max(res.mx, suf + o.pre);
    return res;
  }
};
template <class T>
struct ST {
  vector<T> st;
  int n;
  T ini;
  ST(int n, T ini) : st(2 * n, ini), n(n), ini(ini) {}
  void upd(int pos, T val) {
    for (st[pos += n] = val; pos /= 2;) st[pos] = st[2 * pos] + st[2 * pos + 1];
  }
  T query(int x, int y) {
    T ra = ini, rb = ini;
    for (x += n, y += n + 1; x < y; x /= 2, y /= 2) {
      if (x & 1) ra = ra + st[x++];
      if (y & 1) rb = st[--y] + rb;
    }
    return ra + rb;
  }
};
node c(int x) {
  node r;
  r.mx = max(0, x);
  r.suf = max(0, x);
  r.pre = max(0, x);
  r.tot = x;
  return r;
}
void solve() {
  string s;
  cin >> s;
  int n = s.size();
  node nulo;
  nulo.mx = nulo.pre = nulo.suf = nulo.tot = 0;
  ST<node> D(n + 3, nulo), S(n + 3, nulo), A(n + 3, nulo), W(n + 3, nulo);
  for (int i = 1; i <= n; i++) {
    if (s[i - 1] == 'D') {
      D.upd(i, c(1));
      A.upd(i, c(-1));
    } else if (s[i - 1] == 'A') {
      D.upd(i, c(-1));
      A.upd(i, c(1));
    } else if (s[i - 1] == 'W') {
      W.upd(i, c(1));
      S.upd(i, c(-1));
    } else {
      W.upd(i, c(-1));
      S.upd(i, c(1));
    }
  }
  int dx = 0, dy = 0;
  long long best = 1e15;
  int maxx = 0, minx = 0, maxy = 0, miny = 0;
  for (int i = 1; i <= n + 1; i++) {
    int goy1 = W.query(i, n + 1).pre;
    int goy2 = S.query(i, n + 1).pre;
    int gox1 = D.query(i, n + 1).pre;
    int gox2 = A.query(i, n + 1).pre;
    int up = max(maxy, dy + goy1);
    int down = min(miny, dy - goy2);
    int right = max(maxx, dx + gox1);
    int left = min(minx, dx - gox2);
    D.upd(i - 1, c(1));
    A.upd(i - 1, c(-1));
    int R = max(maxx, dx + D.query(i - 1, n + 1).pre);
    int L = min(minx, dx - A.query(i - 1, n + 1).pre);
    best = min(best, 1LL * (up - down + 1) * (R - L + 1));
    A.upd(i - 1, c(1));
    D.upd(i - 1, c(-1));
    R = max(maxx, dx + D.query(i - 1, n + 1).pre);
    L = min(minx, dx - A.query(i - 1, n + 1).pre);
    best = min(best, 1LL * (up - down + 1) * (R - L + 1));
    W.upd(i - 1, c(1));
    S.upd(i - 1, c(-1));
    R = max(maxy, dy + W.query(i - 1, n + 1).pre);
    L = min(miny, dy - S.query(i - 1, n + 1).pre);
    best = min(best, 1LL * (right - left + 1) * (R - L + 1));
    S.upd(i - 1, c(1));
    W.upd(i - 1, c(-1));
    R = max(maxy, dy + W.query(i - 1, n + 1).pre);
    L = min(miny, dy - S.query(i - 1, n + 1).pre);
    best = min(best, 1LL * (right - left + 1) * (R - L + 1));
    if (i == n + 1) break;
    if (s[i - 1] == 'D')
      dx++;
    else if (s[i - 1] == 'A')
      dx--;
    else if (s[i - 1] == 'S')
      dy--;
    else
      dy++;
    maxx = max(dx, maxx);
    minx = min(dx, minx);
    maxy = max(maxy, dy);
    miny = min(miny, dy);
  }
  best = min(best, 1LL * (maxx - minx + 1) * (maxy - miny + 1));
  cout << best << "\n";
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}
