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.*;
import java.io.*;
 
 
public class Solution{
 
	public static Integer INT(String s){
		return Integer.parseInt(s);
	}
 
	public static Long LONG(String s){
		return Long.parseLong(s);
	}
 
	//====================================================================================================================
 
 	
 
 
	public static void main(String args[])throws IOException{
 
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));	Scanner in=new Scanner(System.in);	StringBuilder out=new StringBuilder();
 		
 		int t=in.nextInt();

 		while(t--!=0)
 			out.append(solve(in.next().toCharArray())+"\n");
 		System.out.print(out);
 	}

 	public static long solve(char cmnd[]){

 		int n=cmnd.length;

 		int prev[][]=new int[4][n+2];
 		int x=0, y=0;
 		int up=0, down=0, left=0, right=0;

 		for(int i=n; i>=1; i--){
 			switch(cmnd[i-1]){
 				case 'S':{ y+=1; up=Math.max(up, y); }break;
 				case 'W':{ y-=1; down=Math.min(down, y); }break;
 				case 'A':{ x+=1; right=Math.max(right, x); }break;
 				case 'D':{ x-=1; left=Math.min(left, x); }break;
 			}
 			prev[0][i]=up-y;
 			prev[1][i]=-(y-down);
 			prev[2][i]=-(x-left);
 			prev[3][i]=right-x;
 		}

 		int next[][]=new int[4][n+2];
 		x=0; y=0;

 		for(int i=1; i<=n; i++){
 			switch(cmnd[i-1]){
 				case 'W':{ y+=1; next[0][i]=Math.max(next[0][i-1], y); }break;
 				case 'S':{ y-=1; next[1][i]=Math.min(next[1][i-1], y); }break;
 				case 'A':{ x-=1; next[2][i]=Math.min(next[2][i-1], x); }break;
 				case 'D':{ x+=1; next[3][i]=Math.max(next[3][i-1], x); }break;
 			}
 			next[0][i]=Math.max(next[0][i-1], next[0][i]);
 			next[1][i]=Math.min(next[1][i-1], next[1][i]);
 			next[2][i]=Math.min(next[2][i-1], next[2][i]);
 			next[3][i]=Math.max(next[3][i-1], next[3][i]);
 		}

 		long min=(next[0][n]-next[1][n]+1L)*(next[3][n]-next[2][n]+1L);
 		x=0; y=0;

 		for(int i=0; i<=n; i++){
 			if(i!=0)
 				switch(cmnd[i-1]){
 					case 'W': y+=1; break;
 					case 'S': y-=1; break;
 					case 'A': x-=1; break;
 					case 'D': x+=1; break;
 				}
 			min=Math.min(min, (Math.max(y+1+prev[0][i+1], next[0][i])-Math.min(y+1+prev[1][i+1], next[1][i])+1L)*(next[3][n]-next[2][n]+1L));
 			min=Math.min(min, (Math.max(y-1+prev[0][i+1], next[0][i])-Math.min(y-1+prev[1][i+1], next[1][i])+1L)*(next[3][n]-next[2][n]+1L));
 			min=Math.min(min, (Math.max(x+1+prev[3][i+1], next[3][i])-Math.min(x+1+prev[2][i+1], next[2][i])+1L)*(next[0][n]-next[1][n]+1L));
 			min=Math.min(min, (Math.max(x-1+prev[3][i+1], next[3][i])-Math.min(x-1+prev[2][i+1], next[2][i])+1L)*(next[0][n]-next[1][n]+1L));
 		}

 		return min;
 	}
}