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() {
  string str;
  int t;
  cin >> t;
  for (int w = 0; w < t; w++) {
    cin >> str;
    int xleft = 0, xright = 0, ytop = 0, ydown = 0;
    bool X = false, Y = false;
    int x = 0, y = 0;
    for (int i = 0; i < str.size(); i++) {
      char c = str[i];
      switch (c) {
        case 'D':
          x++;
          xright = max(x, xright);
          break;
        case 'W':
          y++;
          ytop = max(y, ytop);
          break;
        case 'A':
          x--;
          xleft = min(x, xleft);
          break;
        case 'S':
          y--;
          ydown = min(y, ydown);
          break;
      }
    }
    x = 0;
    y = 0;
    int x1 = -1, x2 = -1;
    int X1 = -1, X2 = -1;
    for (int i = 0; i < str.size(); i++) {
      char c = str[i];
      switch (c) {
        case 'D':
          x++;
          break;
        case 'W':
          y++;
          break;
        case 'A':
          x--;
          break;
        case 'S':
          y--;
          break;
      }
      if (x == xright && x1 == -1 && xright != 0) {
        x1 = i;
        X1 = i;
      } else if (x == xright) {
        X1 = i;
      }
      if (x == xleft && x2 == -1 && xleft != 0) {
        x2 = i;
        X2 = i;
      } else if (x == xleft) {
        X2 = i;
      }
    }
    if ((xright - xleft > 1) && ((X1 < x2) || (X2 < x1))) {
      X = true;
    }
    x = 0;
    y = 0;
    int y1 = -1, y2 = -1;
    int Y1 = -1, Y2 = -1;
    for (int i = 0; i < str.size(); i++) {
      char c = str[i];
      switch (c) {
        case 'D':
          x++;
          break;
        case 'W':
          y++;
          break;
        case 'A':
          x--;
          break;
        case 'S':
          y--;
          break;
      }
      if (y == ytop && y1 == -1 && ytop != 0) {
        y1 = i;
        Y1 = i;
      } else if (y == ytop) {
        Y1 = i;
      }
      if (y == ydown && y2 == -1 && ydown != 0) {
        y2 = i;
        Y2 = i;
      } else if (y == ydown) {
        Y2 = i;
      }
    }
    if ((ytop - ydown > 1) && ((Y1 < y2) || (Y2 < y1))) {
      Y = true;
    }
    long long sizex = (long long)xright - (long long)xleft + 1LL;
    long long sizey = (long long)ytop - (long long)ydown + 1LL;
    if (X && Y) {
      if (sizex < sizey) {
        sizex--;
      } else {
        sizey--;
      }
    } else if (X) {
      sizex--;
    } else if (Y) {
      sizey--;
    }
    cout << sizex * sizey << endl;
  }
}
