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;
int main() {
  long long t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    bool hor = false;
    bool ver = false;
    long long cantW = 0;
    long long cantA = 0;
    long long cantS = 0;
    long long cantD = 0;
    long long der = 0;
    long long izq = 0;
    long long up = 0;
    long long down = 0;
    long long y = 0;
    long long x = 0;
    for (long long i = 0; i < s.size(); i++) {
      if (s[i] == 'W') {
        y++;
        if (y > up) up = y;
        cantW++;
      } else if (s[i] == 'S') {
        y--;
        if (y < down) down = y;
        cantS++;
      } else if (s[i] == 'A') {
        x--;
        if (x < izq) izq = x;
        cantA++;
      } else if (s[i] == 'D') {
        x++;
        if (x > der) der = x;
        cantD++;
      }
    }
    vector<int> ups(s.size() + 1);
    vector<int> downs(s.size() + 1);
    vector<int> izqs(s.size() + 1);
    vector<int> ders(s.size() + 1);
    x = 0;
    y = 0;
    if (up == 0) ups[0] = 1;
    if (down == 0) downs[0] = 1;
    if (izq == 0) izqs[0] = 1;
    if (der == 0) ders[0] = 1;
    for (long long i = 0; i < s.size(); i++) {
      ups[i + 1] = ups[i];
      downs[i + 1] = downs[i];
      izqs[i + 1] = izqs[i];
      ders[i + 1] = ders[i];
      if (s[i] == 'W') {
        y++;
        if (y == up) ups[i + 1]++;
      } else if (s[i] == 'S') {
        y--;
        if (y == down) downs[i + 1]++;
      } else if (s[i] == 'A') {
        x--;
        if (x == izq) izqs[i + 1]++;
      } else if (s[i] == 'D') {
        x++;
        if (x == der) ders[i + 1]++;
      }
    }
    x = 0;
    y = 0;
    long long up2 = 0;
    long long down2 = 0;
    long long izq2 = 0;
    long long der2 = 0;
    bool cambio = false;
    for (long long i = 0; i < s.size(); i++) {
      if (!cambio && ups[i] < ups[i + 1]) {
        cambio = true;
        y--;
        if (y < down2) down2 = y;
      }
      if (s[i] == 'W') {
        y++;
        if (y > up2) up2 = y;
      } else if (s[i] == 'S') {
        y--;
        if (y < down2) down2 = y;
      }
    }
    if (cambio && up2 < up && down2 >= down) ver = true;
    x = 0;
    y = 0;
    up2 = 0;
    down2 = 0;
    izq2 = 0;
    der2 = 0;
    cambio = false;
    for (long long i = 0; i < s.size(); i++) {
      if (!cambio && downs[i] < downs[i + 1]) {
        cambio = true;
        y++;
        if (y > up2) up2 = y;
      }
      if (s[i] == 'W') {
        y++;
        if (y > up2) up2 = y;
      } else if (s[i] == 'S') {
        y--;
        if (y < down) down2 = y;
      }
    }
    if (cambio && down2 > down && up2 <= up) ver = true;
    x = 0;
    y = 0;
    up2 = 0;
    down2 = 0;
    izq2 = 0;
    der2 = 0;
    cambio = false;
    for (long long i = 0; i < s.size(); i++) {
      if (!cambio && izqs[i] < izqs[i + 1]) {
        cambio = true;
        x++;
      }
      if (s[i] == 'D') {
        x++;
        if (x > der2) der2 = x;
      } else if (s[i] == 'A') {
        x--;
        if (x < izq2) izq2 = x;
      }
    }
    if (cambio && izq2 > izq && der2 <= der) hor = true;
    x = 0;
    y = 0;
    up2 = 0;
    down2 = 0;
    izq2 = 0;
    der2 = 0;
    cambio = false;
    for (long long i = 0; i < s.size(); i++) {
      if (!cambio && ders[i] < ders[i + 1]) {
        cambio = true;
        x--;
      }
      if (s[i] == 'D') {
        x++;
        if (x > der2) der2 = x;
      } else if (s[i] == 'A') {
        x--;
        if (x < izq2) izq2 = x;
      }
    }
    if (cambio && izq2 >= izq && der2 < der) hor = true;
    long long area = 1;
    long long h = der - izq;
    long long v = up - down;
    hor &= (h > 1);
    ver &= (v > 1);
    if (cantW == 0 && cantS == 0 && cantA == 0 && cantD == 0)
      cout << 1 << '\n';
    else if (cantD == 0 && cantA == 0) {
      if (ver) {
        cout << v << '\n';
      } else {
        cout << v + 1 << '\n';
      }
    } else if (cantS == 0 && cantW == 0) {
      if (hor) {
        cout << h << '\n';
      } else {
        cout << h + 1 << '\n';
      }
    } else {
      if (ver && hor) {
        cout << min(h * (v + 1), v * (h + 1)) << '\n';
      } else if (ver) {
        cout << v * (h + 1) << '\n';
      } else if (hor) {
        cout << h * (v + 1) << '\n';
      } else {
        cout << (h + 1) * (v + 1) << '\n';
      }
    }
  }
}
