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).
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author svilen.marchev@gmail.com
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    TaskC solver = new TaskC();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskC {
    static final int[][] OFFSETS = new int[][]{
        // Offsets for row, column. (0,0) is the top left corner.
        new int[]{-1, 0}, // W
        new int[]{+1, 0}, // S
        new int[]{0, -1}, // A
        new int[]{0, +1}, // D
    };

    int[] offsetForMove(char c) {
      switch (c) {
        case 'W':
          return OFFSETS[0];
        case 'S':
          return OFFSETS[1];
        case 'A':
          return OFFSETS[2];
        case 'D':
          return OFFSETS[3];
        default:
          throw new AssertionError();
      }
    }

    char reversePathMove(char c) {
      switch (c) {
        case 'W':
          return 'S';
        case 'S':
          return 'W';
        case 'A':
          return 'D';
        case 'D':
          return 'A';
        default:
          throw new AssertionError();
      }
    }

    String reversePath(String s) {
      StringBuilder sb = new StringBuilder(s);
      sb.reverse();
      for (int i = 0; i < sb.length(); ++i) {
        sb.setCharAt(i, reversePathMove(sb.charAt(i)));
      }
      return sb.toString();
    }

    long tryToAdaptToFit(TaskC.Box reducedBox, TaskC.Point startingPoint, String path) {
      TaskC.Point point = startingPoint;
      TaskC.Box box = new TaskC.Box(point, point);
      if (!reducedBox.contains(point)) {
        return -1;
      }

      boolean hasCorrected = false;
      for (int i = 0; i < path.length(); ++i) {
        int[] off = offsetForMove(path.charAt(i));
        TaskC.Point newPoint = new TaskC.Point(point.r + off[0], point.c + off[1]);
        if (!hasCorrected && !reducedBox.contains(newPoint)) {
          hasCorrected = true;
          // Push an immediate contra-move of this move, so that we stay in the reduced box.
          // We do this simply by ignoring this move, but we need to update the box to
          // account for the extra move.
          int[] contraOff = offsetForMove(reversePathMove(path.charAt(i)));
          TaskC.Point contraPoint = new TaskC.Point(point.r + contraOff[0], point.c + contraOff[1]);
          box = TaskC.Box.copyUpdate(box, contraPoint);
        } else {
          point = newPoint;
          box = TaskC.Box.copyUpdate(box, point);
        }
      }

      return box.area();
    }

    long calcMinReducedArea(String path) {
      // boxFromMove[0] - the bounding box of the whole path, including the point before
      // following any move.
      // boxFromMove[i] - the bounding box from the (i-1)th move on, with the (i-1)th move
      // already done.
      TaskC.Box[] boxFromMove = new TaskC.Box[path.length() + 1];

      String reversedPath = reversePath(path);

      TaskC.Point point = new TaskC.Point(0, 0);
      TaskC.Box box = new TaskC.Box(point, point);
      boxFromMove[path.length()] = box;

      for (int i = 0; i < reversedPath.length(); ++i) {
        int[] off = offsetForMove(reversedPath.charAt(i));
        point = new TaskC.Point(point.r + off[0], point.c + off[1]);
        box = TaskC.Box.copyUpdate(box, point);
        boxFromMove[path.length() - 1 - i] = box;
      }

//    System.out.println(box);
//    System.out.println(box.area());

      TaskC.Box wholeBox = box;
      TaskC.Point startingPoint = point;

      long minArea = wholeBox.area();

      {
        TaskC.Box withoutFirstCol = new TaskC.Box(new TaskC.Point(wholeBox.tl.r, wholeBox.tl.c + 1),
            wholeBox.br);
        long area = tryToAdaptToFit(withoutFirstCol, startingPoint, path);
//      System.out.println("area=" + area);
        if (area != -1) {
          minArea = Math.min(minArea, area);
        }
      }

      {
        TaskC.Box withoutFirstRow = new TaskC.Box(new TaskC.Point(wholeBox.tl.r + 1, wholeBox.tl.c),
            wholeBox.br);
        long area = tryToAdaptToFit(withoutFirstRow, startingPoint, path);
        if (area != -1) {
          minArea = Math.min(minArea, area);
        }
      }

      {
        TaskC.Box withoutLastRow = new TaskC.Box(wholeBox.tl,
            new TaskC.Point(wholeBox.br.r - 1, wholeBox.br.c));
        long area = tryToAdaptToFit(withoutLastRow, startingPoint, path);
        if (area != -1) {
          minArea = Math.min(minArea, area);
        }
      }

      {
        TaskC.Box withoutLastCol = new TaskC.Box(wholeBox.tl,
            new TaskC.Point(wholeBox.br.r, wholeBox.br.c - 1));
        long area = tryToAdaptToFit(withoutLastCol, startingPoint, path);
        if (area != -1) {
          minArea = Math.min(minArea, area);
        }
      }

      return minArea;
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
      int tests = in.readInt();
      for (int test = 0; test < tests; ++test) {
        String path = in.readString();
        out.println(calcMinReducedArea(path));
      }
    }

    static class Point {
      final int r;
      final int c;

      Point(int r, int c) {
        this.r = r;
        this.c = c;
      }


      public String toString() {
        return String.format("(%d,%d)", r, c);
      }

    }

    static class Box {
      final TaskC.Point tl;
      final TaskC.Point br;

      Box(TaskC.Point tl, TaskC.Point br) {
        this.tl = tl;
        this.br = br;
      }

      long area() {
        return ((long) br.r - tl.r + 1) * (br.c - tl.c + 1);
      }


      public String toString() {
        return String.format("%s-%s", tl, br);
      }

      boolean contains(TaskC.Point point) {
        return tl.r <= point.r && point.r <= br.r &&
            tl.c <= point.c && point.c <= br.c;
      }

      static TaskC.Box copyUpdate(TaskC.Box existing, TaskC.Point point) {
        return new TaskC.Box(
            new TaskC.Point(Math.min(existing.tl.r, point.r), Math.min(existing.tl.c, point.c)),
            new TaskC.Point(Math.max(existing.br.r, point.r), Math.max(existing.br.c, point.c)));
      }

    }

  }

  static class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private InputReader.SpaceCharFilter filter;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (numChars == -1) {
        throw new InputMismatchException();
      }
      if (curChar >= numChars) {
        curChar = 0;
        try {
          numChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }
        if (numChars <= 0) {
          return -1;
        }
      }
      return buf[curChar++];
    }

    public int readInt() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = read();
      }
      int res = 0;
      do {
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res *= 10;
        res += c - '0';
        c = read();
      } while (!isSpaceChar(c));
      return res * sgn;
    }

    public String readString() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      StringBuilder res = new StringBuilder();
      do {
        if (Character.isValidCodePoint(c)) {
          res.appendCodePoint(c);
        }
        c = read();
      } while (!isSpaceChar(c));
      return res.toString();
    }

    public boolean isSpaceChar(int c) {
      if (filter != null) {
        return filter.isSpaceChar(c);
      }
      return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
      public boolean isSpaceChar(int ch);

    }

  }
}

