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.BufferedReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;

import javax.swing.text.StyledEditorKit.ForegroundAction;


public class main {
	
	public static void main(String[] args) throws NumberFormatException, IOException
	{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw= new PrintWriter(System.out);
		int T= Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			String s=br.readLine();
			long x=0;
			long y=0;
			long minX=0;
			long maxX=0;
			long minY=0;
			long maxY=0;
			for (int j = 0; j < s.length(); j++) {
				if(s.charAt(j)=='D')
				{
					x++;
				}
				else if(s.charAt(j)=='A')
				{
					x--;
				}
				else if(s.charAt(j)=='W')
				{
					y++;
				}
				else if(s.charAt(j)=='S')
				{
					y--;
				}
				minX=Math.min(minX, x);
				maxX=Math.max(maxX, x);
				minY=Math.min(minY, y);
				maxY=Math.max(maxY, y);
			}
			long distX=maxX-minX+1;
			long distY=maxY-minY+1;
			long area=distX*distY;
			
			boolean moveUsed=false;
			x=0;
			y=0;
			long min_X=0;
			long max_X=0;
			long min_Y=0;
			long max_Y=0;
			for (int j = 0; j < s.length(); j++) {
				if(s.charAt(j)=='D')
				{
					x++;
				}
				else if(s.charAt(j)=='A')
				{
					if(!moveUsed && x==minX+1)
					{
						moveUsed=true;
						x++;
						min_X=Math.min(min_X, x);
						max_X=Math.max(max_X, x);
						min_Y=Math.min(min_Y, y);
						max_Y=Math.max(max_Y, y);
					}
					x--;
				}
				else if(s.charAt(j)=='W')
				{
					y++;
				}
				else if(s.charAt(j)=='S')
				{
					y--;
				}
			
				min_X=Math.min(min_X, x);
				max_X=Math.max(max_X, x);
				min_Y=Math.min(min_Y, y);
				max_Y=Math.max(max_Y, y);
			}

			distX=max_X-min_X+1;
			distY=max_Y-min_Y+1;
			area=Math.min(area,distX*distY);
			moveUsed=false;
			x=0;
			y=0;
			min_X=0;
			max_X=0;
			min_Y=0;
			max_Y=0;
			for (int j = 0; j < s.length(); j++) {
				if(s.charAt(j)=='D')
				{
					if(!moveUsed && x==maxX-1)
					{
						moveUsed=true;
						x--;
						min_X=Math.min(min_X, x);
						max_X=Math.max(max_X, x);
						min_Y=Math.min(min_Y, y);
						max_Y=Math.max(max_Y, y);
					}
					x++;
				}
				else if(s.charAt(j)=='A')
				{
					x--;
				}
				else if(s.charAt(j)=='W')
				{
					y++;
				}
				else if(s.charAt(j)=='S')
				{
					y--;
				}
				min_X=Math.min(min_X, x);
				max_X=Math.max(max_X, x);
				min_Y=Math.min(min_Y, y);
				max_Y=Math.max(max_Y, y);
			}
			distX=max_X-min_X+1;
			distY=max_Y-min_Y+1;
			area=Math.min(area,distX*distY);
			moveUsed=false;
			x=0;
			y=0;
			min_X=0;
			max_X=0;
			min_Y=0;
			max_Y=0;
			for (int j = 0; j < s.length(); j++) {
				if(s.charAt(j)=='D')
				{
					x++;
				}
				else if(s.charAt(j)=='A')
				{
					x--;
				}
				else if(s.charAt(j)=='W')
				{
					y++;
				}
				else if(s.charAt(j)=='S')
				{
					if(!moveUsed && y==minY+1)
					{
						moveUsed=true;
						y++;
						min_X=Math.min(min_X, x);
						max_X=Math.max(max_X, x);
						min_Y=Math.min(min_Y, y);
						max_Y=Math.max(max_Y, y);
					}
					y--;
				}
				min_X=Math.min(min_X, x);
				max_X=Math.max(max_X, x);
				min_Y=Math.min(min_Y, y);
				max_Y=Math.max(max_Y, y);
			}
			distX=max_X-min_X+1;
			distY=max_Y-min_Y+1;
			area=Math.min(area,distX*distY);
			
			moveUsed=false;
			x=0;
			y=0;
			min_X=0;
			max_X=0;
			min_Y=0;
			max_Y=0;
			for (int j = 0; j < s.length(); j++) {
				if(s.charAt(j)=='D')
				{
					x++;
				}
				else if(s.charAt(j)=='A')
				{
					x--;
				}
				else if(s.charAt(j)=='W')
				{
					if(!moveUsed && y==maxY-1)
					{
						moveUsed=true;
						y--;
						min_X=Math.min(min_X, x);
						max_X=Math.max(max_X, x);
						min_Y=Math.min(min_Y, y);
						max_Y=Math.max(max_Y, y);
					}
					y++;
				}
				else if(s.charAt(j)=='S')
				{
					y--;
				}
				min_X=Math.min(min_X, x);
				max_X=Math.max(max_X, x);
				min_Y=Math.min(min_Y, y);
				max_Y=Math.max(max_Y, y);
			}
			distX=max_X-min_X+1;
			distY=max_Y-min_Y+1;
			area=Math.min(area,distX*distY);
			
			pw.println(area);
		}
		
		pw.close();
	}

}
