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.*;
import java.util.*;

public class C {

	class Pair{
		long a;
		int b;
		Pair(int a, int b){this.a = a; this.b = b;}
	}

	Pair can(int v[]){
		int n = v.length;		
		int p = 0, i, minP = 0, maxP = 0;
		for(i=0;i<n;i++){
			p += v[i];
			minP = Math.min(minP, p);
			maxP = Math.max(maxP, p);
		}
		int pp = maxP - minP + 1;
		if(maxP - minP + 1 <= 2)
			return new Pair(pp, 0);

		int lMin=-1,rMin=-1,lMax=0,rMax=0;
		p = 0;
		for(i=0;i<=n;i++){
			if(p == minP){
				if(lMin < 0) lMin = i;
				lMax = i;
			}
			if(p == maxP){
				if(rMin < 0) rMin = i;
				rMax = i;
			}
			if(i < n)
				p += v[i];
		}
		if(lMax < rMin || rMax < lMin)
			return new Pair(pp, 1);
		return new Pair(pp, 0);
	}

	void run() {
		char s[] = in.next().toCharArray();

		ArrayList<Integer> lh = new ArrayList<>();
		ArrayList<Integer> lv = new ArrayList<>();

		int i;
		for(i=0;i<s.length;i++){
			if(s[i] == 'W'){
				lv.add(1);
			}else if(s[i] == 'S'){
				lv.add(-1);
			}else if(s[i] == 'A'){
				lh.add(1);
			}else if(s[i] == 'D'){
				lh.add(-1);
			}
		}
		
		Pair p1 = can(lh.stream().mapToInt(ii -> ii.intValue()).toArray());
		Pair p2 = can(lv.stream().mapToInt(ii -> ii.intValue()).toArray());

		long ans = p1.a * p2.a;
		if(p1.b > 0){
			ans = Math.min(ans, (p1.a - 1) * p2.a);
		}
		if(p2.b > 0){
			ans = Math.min(ans, p1.a * (p2.a-1));
		}
		out.println(ans);
	}
	
	static MyScanner in;
	static PrintWriter out;

	public static void main(String[] args) throws IOException {
		boolean stdStream = true;
		if(stdStream){
			in = new MyScanner();
			out = new PrintWriter(System.out);
		}else{
			String fileName = C.class.getSimpleName();
			int n_test = 1;			
			String inputFileName = fileName + String.format(".%02d", n_test) + ".inp";
			String outputFileName = fileName + String.format(".%02d", n_test) + ".out";
			in = new MyScanner(new BufferedReader(new FileReader(inputFileName)));
			out = new PrintWriter(outputFileName);
		}
		
		int nq = in.nextI();
		while(nq-- > 0)
			new C().run();

		in.close();
		out.close();
	}

	static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

        MyScanner(){
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

		MyScanner(BufferedReader br) {
			this.br = br;
        }

        void close() throws IOException {
            br.close();
        }
        
		void findToken() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		
		String next() {
			findToken();
			return st.nextToken();
		}
		
		int nextI() {
			return Integer.parseInt(next());
		}

		int[] nextI(int n) {
			int v[] = new int[n];
			for(int i=0;i<n;i++) v[i] = nextI();
			return v;
		}
		
		long nextL() {
			return Long.parseLong(next());
		}

		long[] nextL(int n) {
			long v[] = new long[n];
			for(int i=0;i<n;i++) v[i] = nextL();
			return v;
		}
		
		double nextD() {
			return Double.parseDouble(next());
		}

		double[] nextD(int n) {
			double v[] = new double[n];
			for(int i=0;i<n;i++) v[i] = nextD();
			return v;
		}
	}
}