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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class YouAreGivenAWASDString {
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	public static StringTokenizer st;
	
	public static void main(String[] args) throws IOException {
		int t = nextInt();
		for (int tt = 0; tt < t; tt++) {
			String s = nextString();
			long[] a = f(s);
			long min = a[4];
			for (int i = 0; i < 4; i++) {
				String r = s.substring(0, (int) a[i]) + "DAWS".charAt(i) + s.substring((int) a[i]);
				min = Math.min(min, f(r)[4]);
			}
			
			System.out.println(min);
		}
	}
	
	public static long[] f(String s) {
		int[] a = new int[2];
		int[][] b = new int[2][2];
		int[][] c = new int[2][2];
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == 'D')
				a[0]++;
			else if (s.charAt(i) == 'A')
				a[0]--;
			else if (s.charAt(i) == 'W')
				a[1]++;
			else
				a[1]--;
			
			for (int j = 0; j < 2; j++) {
				if (a[j] < b[j][0]) {
					b[j][0] = a[j];
					c[j][0] = i;
				}
				if (a[j] > b[j][1]) {
					b[j][1] = a[j];
					c[j][1] = i;
				}
			}
		}
		
		long[] ret = new long[5];
		for (int i = 0; i < 4; i++)
			ret[i] = c[i/2][i%2];
		ret[4] = 1l*(b[0][1]-b[0][0]+1)*(b[1][1]-b[1][0]+1);
		return ret;
	}
	
	public static String nextLine() throws IOException {
		return in.readLine();
	}

	public static String nextString() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}

	public static int nextInt() throws IOException {
		return Integer.parseInt(nextString());
	}

	public static long nextLong() throws IOException {
		return Long.parseLong(nextString());
	}

	public static int[] intArray(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public static int[][] intArray(int n, int m) throws IOException {
		int[][] a = new int[n][m];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				a[i][j] = nextInt();
		return a;
	}

	public static long[] longArray(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}