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>
template <typename T>
class IntegerIterator {
 public:
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T *;
  using reference = T;
  using iterator_category = std::input_iterator_tag;
  explicit IntegerIterator(T value) : value(value) {}
  IntegerIterator &operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator &operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) const { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) const { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
  using IteratorType = std::reverse_iterator<IntegerIterator<T>>;

 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IteratorType begin() const {
    return IteratorType(IntegerIterator<T>(begin_));
  }
  IteratorType end() const { return IteratorType(IntegerIterator<T>(end_)); }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  return ReversedIntegerRange<T>(from + 1, to);
}
using namespace std;
class CYouAreGivenAWASDString {
 public:
  void solve(std::istream &in, std::ostream &out) {
    int t;
    in >> t;
    while (t--) {
      string str;
      in >> str;
      int n = str.size();
      vector<int> maxx1(n + 1), minx1(n + 1), maxy1(n + 1), miny1(n + 1),
          maxx2(n + 1), maxy2(n + 1), minx2(n + 1), miny2(n + 1);
      int x = 0, y = 0;
      for (int i : range(n)) {
        if (str[i] == 'W') {
          y++;
        } else if (str[i] == 'S') {
          y--;
        } else if (str[i] == 'A') {
          x--;
        } else {
          x++;
        }
        minx1[i + 1] = min(minx1[i], x);
        maxx1[i + 1] = max(maxx1[i], x);
        miny1[i + 1] = min(miny1[i], y);
        maxy1[i + 1] = max(maxy1[i], y);
      }
      minx2[n] = maxx2[n] = x;
      miny2[n] = maxy2[n] = y;
      for (int i : downrange(n)) {
        if (str[i] == 'W') {
          y--;
        } else if (str[i] == 'S') {
          y++;
        } else if (str[i] == 'A') {
          x++;
        } else {
          x--;
        }
        minx2[i] = min(minx2[i + 1], x);
        maxx2[i] = max(maxx2[i + 1], x);
        miny2[i] = min(miny2[i + 1], y);
        maxy2[i] = max(maxy2[i + 1], y);
      }
      long long res =
          (long long)(maxx1[n] - minx1[n] + 1) * (maxy1[n] - miny1[n] + 1);
      for (int i : inclusiveRange(0, n)) {
        for (int j : range(4)) {
          int dx = 0, dy = 0;
          if (j % 2 == 0) {
            if (j / 2) {
              dx = 1;
            } else {
              dx = -1;
            }
          } else {
            if (j / 2) {
              dy = 1;
            } else {
              dy = -1;
            }
          }
          int maxX = max(maxx1[i], maxx2[i] + dx),
              minX = min(minx1[i], minx2[i] + dx),
              maxY = max(maxy1[i], maxy2[i] + dy),
              minY = min(miny1[i], miny2[i] + dy);
          res = min(res, (long long)(maxX - minX + 1) * (maxY - minY + 1));
        }
      }
      out << res << "\n";
    }
  }
  void setup() {}
};
int main() {
  std::ios_base::sync_with_stdio(false);
  CYouAreGivenAWASDString solver;
  solver.setup();
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  in.tie(nullptr);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}
