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;
const int maxn = 2e5 + 10;
char s[maxn];
struct matrix {
  int x1, y1, x2, y2;
} st[maxn], ed[maxn];
inline int getx(char t) {
  if (t == 'W' || t == 'S') return 0;
  if (t == 'D') return 1;
  return -1;
}
inline int gety(char t) {
  if (t == 'A' || t == 'D') return 0;
  if (t == 'W') return 1;
  return -1;
}
void update(int x, int y, matrix &a) {
  if (x < a.x1) a.x1 = x;
  if (x > a.x2) a.x2 = x;
  if (y < a.y1) a.y1 = y;
  if (y > a.y2) a.y2 = y;
}
matrix move(char t, matrix &a) {
  matrix re = a;
  re.x1 += getx(t), re.x2 += getx(t);
  re.y1 += gety(t), re.y2 += gety(t);
  return re;
}
long long getsize(matrix a, matrix b) {
  long long mnx, mny, mxx, mxy;
  mnx = a.x1 < b.x1 ? a.x1 : b.x1;
  mny = a.y1 < b.y1 ? a.y1 : b.y1;
  mxx = a.x2 > b.x2 ? a.x2 : b.x2;
  mxy = a.y2 > b.y2 ? a.y2 : b.y2;
  return (mxx - mnx + 1) * (mxy - mny + 1);
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s);
    int x = 0, y = 0, n = strlen(s);
    matrix rg = (matrix){0, 0, 0, 0};
    for (int i = 0; i < n; i++) {
      st[i] = rg;
      x += getx(s[i]), y += gety(s[i]);
      update(x, y, rg);
    }
    st[n] = rg;
    rg = (matrix){x, y, x, y};
    ed[n] = rg;
    for (int i = n - 1; i >= 0; i--) {
      x -= getx(s[i]), y -= gety(s[i]);
      update(x, y, rg);
      ed[i] = rg;
    }
    long long ans = 1e18;
    for (int i = 0; i <= n; i++) {
      long long val;
      val = getsize(st[i], move('W', ed[i]));
      if (val < ans) ans = val;
      val = getsize(st[i], move('A', ed[i]));
      if (val < ans) ans = val;
      val = getsize(st[i], move('S', ed[i]));
      if (val < ans) ans = val;
      val = getsize(st[i], move('D', ed[i]));
      if (val < ans) ans = val;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
