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.util.*;
public class Main {
    public static class Point {
        long row, col;
        public Point(long row, long col) {
            this.row = row;
            this.col = col;
        }
        public Point w() {
            return new Point(row - 1, col);
        }
        public Point a() {
            return new Point(row, col - 1);
        }
        public Point s() {
            return new Point(row + 1, col);
        }
        public Point d() {
            return new Point(row, col + 1);
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            String s = in.next();
            Point[] arr = new Point[s.length() + 1];
            arr[0] = new Point(0, 0);
            long minX, maxX, minY, maxY;
            minX = maxX = minY = maxY = 0;
            for (int j = 1; j <= s.length(); j++) {
                switch(s.charAt(j - 1)) {
                    case 'W':
                        arr[j] = arr[j - 1].w();
                        break;
                    case 'A':
                        arr[j] = arr[j - 1].a();
                        break;
                    case 'S':
                        arr[j] = arr[j - 1].s();
                        break;
                    case 'D':
                        arr[j] = arr[j - 1].d();
                        break;
                }
                minX = Math.min(minX, arr[j].row);
                maxX = Math.max(maxX, arr[j].row);
                minY = Math.min(minY, arr[j].col);
                maxY = Math.max(maxY, arr[j].col);
            }
            long area = (maxY - minY + 1) * (maxX - minX + 1);
            if (maxX - minX >= 2) {
                boolean activated = false;
                boolean reached = false;
                for (Point p : arr) {
                    if (p.row == minX) {
                        activated = true;
                    }
                    long curr = p.row + (activated ? 1 : 0);
                    if (curr > maxX) {
                        reached = true;
                    }
                }
                if (!reached) {
                    area = Math.min(area, (maxY - minY + 1) * (maxX - minX));
                }
                activated = false;
                reached = false;
                for (Point p : arr) {
                    if (p.row == maxX) {
                        activated = true;
                    }
                    long curr = p.row - (activated ? 1 : 0);
                    if (curr < minX) {
                        reached = true;
                    }
                }
                if (!reached) {
                    area = Math.min(area, (maxY - minY + 1) * (maxX - minX));
                }
            }
            if (maxY - minY >= 2) {
                boolean activated = false;
                boolean reached = false;
                for (Point p : arr) {
                    if (p.col == minY) {
                        activated = true;
                    }
                    long curr = p.col + (activated ? 1 : 0);
                    if (curr > maxY) {
                        reached = true;
                    }
                }
                if (!reached) {
                    area = Math.min(area, (maxY - minY) * (maxX - minX + 1));
                }
                activated = false;
                reached = false;
                for (Point p : arr) {
                    if (p.col == maxY) {
                        activated = true;
                    }
                    long curr = p.col - (activated ? 1 : 0);
                    if (curr < minY) {
                        reached = true;
                    }
                }
                if (!reached) {
                    area = Math.min(area, (maxY - minY) * (maxX - minX + 1));
                }
            }
            System.out.println(area);
        }
    }
}