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;
int gcd(int a, int b) {
  int c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}
struct UnionFind {
  vector<int> par;
  UnionFind(int N) : par(N) {
    for (int i = 0; i < N; i++) par[i] = i;
  }
  int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  void unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    if (rx == ry) return;
    par[rx] = ry;
  }
  bool same(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};
long long M = 1000000007;
vector<long long> fac(300001);
vector<long long> ifac(300001);
long long mpow(long long x, long long n) {
  long long ans = 1;
  while (n != 0) {
    if (n & 1) ans = ans * x % M;
    x = x * x % M;
    n = n >> 1;
  }
  return ans;
}
void setcomb() {
  fac[0] = 1;
  ifac[0] = 1;
  for (long long i = 0; i < 1000000; i++) {
    fac[i + 1] = fac[i] * (i + 1) % M;
  }
  ifac[1000000] = mpow(fac[1000000], M - 2);
  for (long long i = 1000000; i > 0; i--) {
    ifac[i - 1] = ifac[i] * i % M;
  }
}
long long comb(long long a, long long b) {
  if (a == 0 && b == 0) return 1;
  if (a < b || a < 0) return 0;
  long long tmp = ifac[a - b] * ifac[b] % M;
  return tmp * fac[a] % M;
}
long long perm(long long a, long long b) {
  if (a == 0 && b == 0) return 1;
  if (a < b || a < 0) return 0;
  return fac[a] * ifac[a - b] % M;
}
long long modinv(long long a) {
  long long b = M, u = 1, v = 0;
  while (b) {
    long long t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= M;
  if (u < 0) u += M;
  return u;
}
vector<vector<long long>> mul(vector<vector<long long>> a,
                              vector<vector<long long>> b, int n) {
  int i, j, k, t;
  vector<vector<long long>> c(n);
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      t = 0;
      for (k = 0; k < n; k++) t = (t + a[i][k] * b[k][j] % M) % M;
      c[i].push_back(t);
    }
  }
  return c;
}
template <typename Monoid>
struct SegmentTree {
  int sz;
  vector<Monoid> seg;
  const Monoid M1;
  SegmentTree(int n, const Monoid &M1) : M1(M1) {
    sz = 1;
    while (sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }
  void set(int k, const Monoid &x) { seg[k + sz] = x; }
  void build() {
    for (int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = f(L, seg[a++]);
      if (b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
  Monoid value(const int &k) const { return seg[k + sz]; }
  Monoid f(Monoid a, Monoid b) { return a + b; }
};
int main() {
  long long t, i, j, k, ans, l, r, d, u, x, y, cl, cr, cd, cu, fx, fy;
  cin >> t;
  for (i = 0; i < t; i++) {
    l = 0;
    r = 0;
    d = 0;
    u = 0;
    x = 0;
    y = 0;
    fx = 1;
    fy = 1;
    cl = 1;
    cd = 1;
    cu = 1;
    cr = 1;
    string s;
    cin >> s;
    for (j = 0; j < s.size(); j++) {
      if (s[j] == 'W') {
        y++;
        if (y == u) {
          if (cd == 1) fy = 1;
          cu = 1;
        } else if (y > u) {
          u++;
          cd = 0;
          cu = 1;
          fy = 0;
        }
      } else if (s[j] == 'S') {
        y--;
        if (y == d) {
          if (cu == 1) fy = 1;
          cd = 1;
        } else if (y < d) {
          d--;
          cu = 0;
          cd = 1;
          fy = 0;
        }
      } else if (s[j] == 'D') {
        x++;
        if (x == r) {
          if (cl == 1) fx = 1;
          cr = 1;
        } else if (x > r) {
          r++;
          cl = 0;
          cr = 1;
          fx = 0;
        }
      } else {
        x--;
        if (x == l) {
          if (cr == 1) fx = 1;
          cl = 1;
        } else if (x < l) {
          l--;
          cr = 0;
          cl = 1;
          fx = 0;
        }
      }
    }
    ans = (r - l + 1) * (u - d + 1);
    if (fx == 0 && r - l > 1) ans = min(ans, (r - l) * (u - d + 1));
    if (fy == 0 && u - d > 1) ans = min(ans, (r - l + 1) * (u - d));
    cout << ans << endl;
  }
}
