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;
using ll = long long int;
using int64 = long long int;
template <typename T>
void chmax(T &a, T b) {
  a = max(a, b);
}
template <typename T>
void chmin(T &a, T b) {
  a = min(a, b);
}
template <typename T>
void chadd(T &a, T b) {
  a = a + b;
}
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
template <typename MonoidType>
struct SegmentTree {
  using Function = function<MonoidType(MonoidType, MonoidType)>;
  int n;
  vector<MonoidType> node;
  MonoidType E0;
  Function upd_f, cmb_f;
  void build(int m, vector<MonoidType> v = vector<MonoidType>()) {
    if (v != vector<MonoidType>()) m = v.size();
    n = 1;
    while (n < m) n *= 2;
    node = vector<MonoidType>(2 * n - 1, E0);
    if (v != vector<MonoidType>()) {
      for (int i = 0; i < m; i++) {
        node[n - 1 + i] = v[i];
      }
      for (int i = n - 2; i >= 0; i--) {
        node[i] = cmb_f(node[2 * i + 1], node[2 * i + 2]);
      }
    }
  }
  SegmentTree() {}
  SegmentTree(int n_, MonoidType E0_, Function upd_f_, Function cmb_f_,
              vector<MonoidType> v = vector<MonoidType>())
      : E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_) {
    build(n_, v);
  }
  void update(int k, MonoidType x) {
    k += n - 1;
    node[k] = upd_f(node[k], x);
    while (k > 0) {
      k = (k - 1) / 2;
      node[k] = cmb_f(node[2 * k + 1], node[2 * k + 2]);
    }
  }
  MonoidType query(int a, int b) {
    MonoidType vl = E0, vr = E0;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = cmb_f(vl, node[(l++) - 1]);
      if (r & 1) vr = cmb_f(node[(--r) - 1], vr);
    }
    return cmb_f(vl, vr);
  }
};
auto f = [](int a, int b) { return min(a, b); };
auto g = [](int a, int b) { return max(a, b); };
const int E_MIN = 1 << 28;
const int E_MAX = -E_MIN;
void solve() {
  string s;
  cin >> s;
  int N = s.length();
  vector<int> ud(N + 1), lr(N + 1);
  for (int i = 0; i < N; i++) {
    ud[i + 1] = ud[i];
    lr[i + 1] = lr[i];
    if (s[i] == 'W') ud[i + 1]++;
    if (s[i] == 'S') ud[i + 1]--;
    if (s[i] == 'A') lr[i + 1]--;
    if (s[i] == 'D') lr[i + 1]++;
  }
  SegmentTree<int> seg_min_ud(N + 1, E_MIN, f, f, ud);
  SegmentTree<int> seg_min_lr(N + 1, E_MIN, f, f, lr);
  SegmentTree<int> seg_max_ud(N + 1, E_MAX, g, g, ud);
  SegmentTree<int> seg_max_lr(N + 1, E_MAX, g, g, lr);
  ll ans = 0, R = N + 1;
  {
    ll diff_x = seg_max_lr.query(0, R) - seg_min_lr.query(0, R) + 1;
    ll diff_y = seg_max_ud.query(0, R) - seg_min_ud.query(0, R) + 1;
    ans = diff_x * diff_y;
  }
  for (ll i = 1; i <= N; i++) {
    ll lmax_x = seg_max_lr.query(0, i);
    ll lmax_y = seg_max_ud.query(0, i);
    ll lmin_x = seg_min_lr.query(0, i);
    ll lmin_y = seg_min_ud.query(0, i);
    ll rmax_x = seg_max_lr.query(i, R);
    ll rmax_y = seg_max_ud.query(i, R);
    ll rmin_x = seg_min_lr.query(i, R);
    ll rmin_y = seg_min_ud.query(i, R);
    for (ll k = 0; k < 4; k++) {
      ll lmax_x_p = max<ll>(lmax_x, lr[i - 1] + dx[k]);
      ll lmin_x_p = min<ll>(lmin_x, lr[i - 1] + dx[k]);
      ll lmax_y_p = max<ll>(lmax_y, ud[i - 1] + dy[k]);
      ll lmin_y_p = min<ll>(lmin_y, ud[i - 1] + dy[k]);
      ll rmax_x_p = rmax_x + dx[k];
      ll rmin_x_p = rmin_x + dx[k];
      ll rmax_y_p = rmax_y + dy[k];
      ll rmin_y_p = rmin_y + dy[k];
      ll diff_x = max(rmax_x_p, lmax_x_p) - min(rmin_x_p, lmin_x_p) + 1;
      ll diff_y = max(rmax_y_p, lmax_y_p) - min(rmin_y_p, lmin_y_p) + 1;
      ans = min(ans, diff_x * diff_y);
    }
  }
  printf("%lld\n", ans);
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) solve();
  return 0;
}
