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;
template <typename T>
inline T& back(vector<T>& vec) {
  return *(vec.end() - 1);
}
template <typename T>
inline void pop(vector<T>& vec) {
  return vec.erase(vec.end() - 1);
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> iter) {
  out << "[";
  for (auto t : iter) {
    out << t << ", ";
  }
  out << "]";
  return out;
}
template <typename T>
void printArray(ostream& out, T* arr, int sz) {
  out << "[";
  for (int i = 0; i < sz; i++) {
    out << arr[i] << ", ";
  }
  out << "]";
}
void scan() {}
template <typename F, typename... R>
void scan(F& f, R&... r) {
  cin >> f;
  scan(r...);
}
int di_;
string dnms_, co_ = ",";
void debug_() { cout << endl; }
template <typename F, typename... R>
void debug_(F f, R... r) {
  while (dnms_[di_] != ',') cout << dnms_[di_++];
  di_++;
  cout << ": " << f << ",";
  debug_(r...);
}
struct px {
  long long x, y;
};
const int MN = 2e5 + 1;
string s;
int n;
px pos[MN], pfxMin[MN], pfxMax[MN], sfxMin[MN], sfxMax[MN];
const int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int sssss;
  scan(sssss);
  while (sssss--) {
    scan(s);
    n = s.length();
    pos[(0)] = pfxMin[(0)] = pfxMax[(0)] = sfxMin[(0)] = sfxMax[(0)] = {0, 0};
    for (int i = 1; i <= n; i++) {
      switch (s[i - 1]) {
        case 'D':
          pos[(i)] = pfxMin[(i)] = pfxMax[(i)] = sfxMin[(i)] =
              sfxMax[(i)] = {pos[i - 1].x, pos[i - 1].y + 1};
          break;
        case 'A':
          pos[(i)] = pfxMin[(i)] = pfxMax[(i)] = sfxMin[(i)] =
              sfxMax[(i)] = {pos[i - 1].x, pos[i - 1].y - 1};
          break;
        case 'S':
          pos[(i)] = pfxMin[(i)] = pfxMax[(i)] = sfxMin[(i)] =
              sfxMax[(i)] = {pos[i - 1].x + 1, pos[i - 1].y};
          break;
        case 'W':
          pos[(i)] = pfxMin[(i)] = pfxMax[(i)] = sfxMin[(i)] =
              sfxMax[(i)] = {pos[i - 1].x - 1, pos[i - 1].y};
          break;
      }
    }
    for (int i = 1; i <= n; i++) {
      pfxMin[i].x = min(pfxMin[i].x, pfxMin[i - 1].x);
      pfxMin[i].y = min(pfxMin[i].y, pfxMin[i - 1].y);
      pfxMax[i].x = max(pfxMax[i].x, pfxMax[i - 1].x);
      pfxMax[i].y = max(pfxMax[i].y, pfxMax[i - 1].y);
    }
    for (int i = n - 1; i >= 0; i--) {
      sfxMin[i].x = min(sfxMin[i].x, sfxMin[i + 1].x);
      sfxMin[i].y = min(sfxMin[i].y, sfxMin[i + 1].y);
      sfxMax[i].x = max(sfxMax[i].x, sfxMax[i + 1].x);
      sfxMax[i].y = max(sfxMax[i].y, sfxMax[i + 1].y);
    }
    long long bestArea =
        (pfxMax[n].x - pfxMin[n].x + 1) * (pfxMax[n].y - pfxMin[n].y + 1);
    for (int i = 1; i <= n; i++) {
      for (auto dir : DIRS) {
        long long xMin, yMin, xMax, yMax;
        xMin = min(pos[i - 1].x + dir[0],
                   min(pfxMin[i - 1].x, sfxMin[i].x + dir[0]));
        xMax = max(pos[i - 1].x + dir[0],
                   max(pfxMax[i - 1].x, sfxMax[i].x + dir[0]));
        yMin = min(pos[i - 1].y + dir[1],
                   min(pfxMin[i - 1].y, sfxMin[i].y + dir[1]));
        yMax = max(pos[i - 1].y + dir[1],
                   max(pfxMax[i - 1].y, sfxMax[i].y + dir[1]));
        bestArea = min(bestArea, (xMax - xMin + 1) * (yMax - yMin + 1));
      }
    }
    cout << bestArea << "\n";
  }
  return 0;
}
