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).
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF1202C extends PrintWriter {
	CF1202C() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1202C o = new CF1202C(); o.main(); o.flush();
	}

	int[] dx = { -1, 1, 0, 0 };
	int[] dy = { 0, 0, -1, 1 };
	void main() {
		int t = sc.nextInt();
		while (t-- > 0) {
			byte[] cc = sc.next().getBytes();
			int n = cc.length, inf = n + 1, x0, x1, y0, y1, x, y;
			x0 = y0 = inf; x1 = y1 = -inf; x = y = 0;
			int[] px0 = new int[n + 1];
			int[] px1 = new int[n + 1];
			int[] py0 = new int[n + 1];
			int[] py1 = new int[n + 1];
			for (int i = 0; i <= n; i++) {
				x0 = Math.min(x0, x);
				x1 = Math.max(x1, x);
				y0 = Math.min(y0, y);
				y1 = Math.max(y1, y);
				px0[i] = x0 - x;
				px1[i] = x1 - x;
				py0[i] = y0 - y;
				py1[i] = y1 - y;
				if (i == n)
					break;
				byte c = cc[i];
				if (c == 'W') y++;
				else if (c == 'S') y--;
				else if (c == 'A') x--;
				else x++;
			}
			x0 = y0 = inf; x1 = y1 = -inf; x = y = 0;
			int[] qx0 = new int[n + 1];
			int[] qx1 = new int[n + 1];
			int[] qy0 = new int[n + 1];
			int[] qy1 = new int[n + 1];
			for (int i = n; i >= 0; i--) {
				x0 = Math.min(x0, x);
				x1 = Math.max(x1, x);
				y0 = Math.min(y0, y);
				y1 = Math.max(y1, y);
				qx0[i] = x0 - x;
				qx1[i] = x1 - x;
				qy0[i] = y0 - y;
				qy1[i] = y1 - y;
				if (i == 0)
					break;
				byte c = cc[i - 1];
				if (c == 'W') y--;
				else if (c == 'S') y++;
				else if (c == 'A') x++;
				else x--;
			}
			long ans = 0x3f3f3f3f3f3f3f3fL;
			for (int i = 0; i <= n; i++)
				for (int h = 0; h < 4; h++) {
					x0 = Math.min(px0[i], qx0[i] + dx[h]);
					x1 = Math.max(px1[i], qx1[i] + dx[h]);
					y0 = Math.min(py0[i], qy0[i] + dy[h]);
					y1 = Math.max(py1[i], qy1[i] + dy[h]);
					ans = Math.min(ans, (long) (x1 - x0 + 1) * (y1 - y0 + 1));
				}
			println(ans);
		}
	}
}
