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;
long long int dxk[] = {0, 0, 1, -1, 1, 1, -1, -1};
long long int dyk[] = {1, -1, 0, 0, 1, -1, 1, -1};
long long int ll_max(long long int a, long long int b, long long int c) {
  return max(a, max(b, c));
}
int int_max(int a, int b, int c) { return max(a, max(b, c)); }
long long int ll_min(long long int a, long long int b, long long int c) {
  return min(a, min(b, c));
}
int int_min(int a, int b, int c) { return min(a, min(b, c)); }
long long int max(int a, long long int b) { return max((long long int)a, b); }
long long int min(int a, long long int b) { return min((long long int)a, b); }
long long int min(long long int a, int b) { return min(a, (long long int)b); }
long long int max(long long int a, int b) { return max(a, (long long int)b); }
long long int dx[] = {0, 0, 1, -1};
long long int dy[] = {1, -1, 0, 0};
long long int power(long long int a, long long int b) {
  if (a == 1) return 1;
  if (b == 0) return 1;
  long long int c = power(a, b / 2);
  long long int res = 1;
  if (b % 2) {
    res = (c * c) % 1000000007;
    res *= a;
    res %= 1000000007;
  } else
    res = ((c * c) % 1000000007);
  return res;
}
long long int modInv(long long int a) {
  return power(a, 1000000007 - 2) % 1000000007;
}
long long int fact[1], inv[1];
void factorial(long long int n) {
  fact[0] = 1;
  for (long long int i = 1; i <= n; i++) {
    fact[i] = fact[i - 1] * i;
    fact[i] %= 1000000007;
  }
}
void InvFactorial(long long int n) {
  inv[0] = 1;
  for (long long int i = 1; i <= n; i++) inv[i] = modInv(fact[i]);
}
long long int ncr(long long int n, long long int r) {
  if (n < r || n < 0 || r < 0) return 0;
  long long int b = inv[n - r];
  long long int c = inv[r];
  long long int a = fact[n] * b;
  a %= 1000000007;
  a *= c;
  a %= 1000000007;
  return a;
}
long long int d[200002], r[200002], u[200002], l[200002];
long long int d1[200002], r1[200002], u1[200002], l1[200002];
int a[200001];
int n;
string s;
void dfs(int v, int i, int j) {
  int h = i + dx[a[v - 1]];
  int h1 = j + dy[a[v - 1]];
  u1[v] = min(h, u1[v - 1]);
  l1[v] = min(h1, l1[v - 1]);
  r1[v] = max(h1, r1[v - 1]);
  d1[v] = max(h, d1[v - 1]);
  if (v != n) dfs(v + 1, h, h1);
  u[v] = min(h, u[v + 1]);
  l[v] = min(h1, l[v + 1]);
  r[v] = max(h1, r[v + 1]);
  d[v] = max(h, d[v + 1]);
}
void solve(int countu) {
  cin >> s;
  n = s.size();
  for (long long int i = 0; i < n + 3; i++) {
    d[i] = 0;
    u[i] = 0;
    r[i] = 0;
    l[i] = 0;
    d1[i] = 0;
    u1[i] = 0;
    r1[i] = 0;
    l1[i] = 0;
  }
  u[n + 1] = 10000000;
  l[n + 1] = 10000000;
  r[n + 1] = -100000000;
  d[n + 1] = -100000000;
  for (long long int i = 0; i < s.size(); i++) {
    if (s[i] == 'W')
      a[i] = 3;
    else if (s[i] == 'S')
      a[i] = 2;
    else if (s[i] == 'A')
      a[i] = 1;
    else
      a[i] = 0;
  }
  dfs(1, 0, 0);
  long long int minn = 7000000000000000000;
  for (long long int i = 1; i < n + 1; i++) {
    long long int l2 = l[i] - 1, r2 = r[i] - 1, u2 = u[i], d2 = d[i];
    u2 = min(u2, u1[i]);
    l2 = min(l2, l1[i]);
    r2 = max(r2, r1[i]);
    d2 = max(d2, d1[i]);
    minn = min(minn, (r2 - l2 + 1) * (d2 - u2 + 1));
    l2 = l[i] + 1, r2 = r[i] + 1, u2 = u[i], d2 = d[i];
    u2 = min(u2, u1[i]);
    l2 = min(l2, l1[i]);
    r2 = max(r2, r1[i]);
    d2 = max(d2, d1[i]);
    minn = min(minn, (r2 - l2 + 1) * (d2 - u2 + 1));
    l2 = l[i], r2 = r[i], u2 = u[i] + 1, d2 = d[i] + 1;
    u2 = min(u2, u1[i]);
    l2 = min(l2, l1[i]);
    r2 = max(r2, r1[i]);
    d2 = max(d2, d1[i]);
    minn = min(minn, (r2 - l2 + 1) * (d2 - u2 + 1));
    l2 = l[i], r2 = r[i], u2 = u[i] - 1, d2 = d[i] - 1;
    u2 = min(u2, u1[i]);
    l2 = min(l2, l1[i]);
    r2 = max(r2, r1[i]);
    d2 = max(d2, d1[i]);
    minn = min(minn, (r2 - l2 + 1) * (d2 - u2 + 1));
    l2 = l[i], r2 = r[i], u2 = u[i], d2 = d[i];
    u2 = min(u2, u1[i]);
    l2 = min(l2, l1[i]);
    r2 = max(r2, r1[i]);
    d2 = max(d2, d1[i]);
    minn = min(minn, (r2 - l2 + 1) * (d2 - u2 + 1));
  }
  cout << minn << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed;
  cerr.tie(NULL);
  cout.precision(10);
  int t = 1;
  cin >> t;
  int countu = 1;
  while (t--) {
    solve(countu);
    countu++;
  }
}
