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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma comment(linker, "/STACK:256000000")
using namespace std;
static const int _ = []() {
  ios::sync_with_stdio(false);
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  return 0;
}();
template <typename T, typename U>
struct par {
  T x;
  U y;
  par() : x(0), y(0) {}
  par(const T& x, const U& y) : x(x), y(y) {}
  bool operator<(const par& other) const {
    if (x == other.x) return y < other.y;
    return x < other.x;
  }
  bool operator>(const par& other) const {
    if (x == other.x) return y > other.y;
    return x > other.x;
  }
  bool operator==(const par& other) const {
    return x == other.x && y == other.y;
  }
  par operator-(const par& b) const { return {x - b.x, y - b.y}; }
  string str() const {
    ostringstream ss;
    ss << "{" << x << "," << y << "}";
    return ss.str();
  }
};
template <class T>
inline vector<T> rv(long long n) {
  vector<T> v(n);
  for (long long i = 0; i < (n); i++) cin >> v[i];
  return v;
}
template <class T>
inline void pv(const vector<T>& v) {
  for (long long i = 0; i < (v.size()); i++) cout << v[i] << " ";
  cout << '\n';
}
template <class T, class U>
inline void amax(T& a, const U& b) {
  if (a < b) a = b;
}
template <class T, class U>
inline void amin(T& a, const U& b) {
  if (a > b) a = b;
}
template <class T, class U>
inline T min(T& a, const U& b) {
  return a > b ? b : a;
}
template <class T, class U>
inline T max(T& a, const U& b) {
  return a < b ? b : a;
}
const long long MOD = 1e9 + 7;
const long long MOD1 = 998244353;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
long long GCD(long long a, long long b) {
  if (a < b) swap(a, b);
  while (b) {
    long long r = a % b;
    a = b;
    b = r;
  }
  return a;
}
struct node {
  long long x, d;
};
vector<long long> vis(10, 0);
long long calc(long long from, long long to, long long a, long long b) {
  queue<node> q;
  q.push({from, 0});
  while (!q.empty()) {
    node n = q.front();
    q.pop();
    if ((n.x + a) % 10 == to) {
      return n.d;
    }
    if ((n.x + b) % 10 == to) {
      return n.d;
    }
    if (!vis[(n.x + a) % 10]) {
      q.push({(n.x + a) % 10, n.d + 1});
      vis[(n.x + a) % 10] = 1;
    }
    if (!vis[(n.x + b) % 10]) {
      q.push({(n.x + b) % 10, n.d + 1});
      vis[(n.x + b) % 10] = 1;
    }
  }
  return -1;
}
vector<vector<long long>> gen(long long a, long long b) {
  vector<vector<long long>> v(10, vector<long long>(10, INT_MAX));
  for (long long i = 0; i < 10; i++)
    for (long long j = 0; j < 10; j++) {
      vector<long long>(10, 0).swap(vis);
      v[i][j] = calc(i, j, a, b);
    }
  return v;
}
int main() {
  long long t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    long long x = 0, y = 0;
    map<long long, vector<long long>> mx, my;
    mx[0].push_back(0);
    my[0].push_back(0);
    for (long long i = 0; i < s.size(); i++) {
      char c = s[i];
      if (c == 'W')
        y++;
      else if (c == 'S')
        y--;
      else if (c == 'A')
        x--;
      else if (c == 'D')
        x++;
      mx[x].push_back(i + 1);
      my[y].push_back(i + 1);
    }
    auto mxx = *mx.rbegin();
    auto mnx = *mx.begin();
    auto mxy = *my.rbegin();
    auto mny = *my.begin();
    bool xok = 0, yok = 0;
    long long xdim = mxx.first - mnx.first + 1,
              ydim = mxy.first - mny.first + 1;
    if (mxx.second.front() > mnx.second.back() + 1 ||
        mnx.second.front() > mxx.second.back() + 1) {
      xok = true;
    }
    if (mxy.second.front() > mny.second.back() + 1 ||
        mny.second.front() > mxy.second.back() + 1) {
      yok = true;
    }
    long long ans = xdim * ydim;
    if (xok && yok) {
      if (xdim > ydim) {
        ydim--;
      } else {
        xdim--;
      }
    } else if (xok) {
      xdim--;
    } else if (yok) {
      ydim--;
    }
    cout << xdim * ydim << endl;
  }
  return 0;
}
