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 Main {
	public static void main(String args[]) {new Main().run();}

	FastReader in = new FastReader();
	PrintWriter out = new PrintWriter(System.out);
	void run(){
		int q=in.nextInt();
		for(int i=0;i<q;i++) {
			work();
		}
		out.flush();
	}
	long mod=1000000007;
	long gcd(long a,long b) {
		return b==0?a:gcd(b,a%b);
	}
	long ret=0;
	long ml,mr,mu,md;
	boolean v,h;
	void work() {
		ml=0;
		mr=0;
		mu=0;
		md=0;
		v=false;
		h=false;
		String s=in.next();
		int n=s.length();
		int[] p=new int[2];
		for(int i=0;i<n;i++) {
			char c=s.charAt(i);
			if(c=='W') p[0]--;
			else if(c=='S') p[0]++;
			else if(c=='A') p[1]--;
			else p[1]++;
			ml=Math.min(p[1], ml);
			mr=Math.max(p[1], mr);
			mu=Math.min(p[0], mu);
			md=Math.max(p[0], md);
		}
		dfs(s,0,0,0,0,0,0,0);
		long ret=(mr-ml+1)*(md-mu+1);
		if(h&&mr-ml>1) {//至少移一步
			ret=Math.min(ret,(md-mu+1)*(mr-ml));
		}
		if(v&&md-mu>1) {
			ret=Math.min(ret,(mr-ml+1)*(md-mu));
		}
		out.println(ret);
	}
	private int[] dfs(String s, int index, int x, int y, int cl, int cr, int cu, int cd) {
		if(index==s.length()) {
			return new int[] {y,y,x,x};
		}
		char c=s.charAt(index);
		int nx=x,ny=y;
		if(c=='W') nx--;
		else if(c=='S') nx++;
		else if(c=='A') ny--;
		else ny++;
		int nl=Math.min(ny, cl);
		int nr=Math.max(ny, cr);
		int nu=Math.min(nx, cu);
		int nd=Math.max(nx, cd);
		int[] p=dfs(s,index+1,nx,ny,nl,nr,nu,nd);//l,r,u,d
		p[0]=Math.min(ny, p[0]);
		p[1]=Math.max(ny, p[1]);
		p[2]=Math.min(nx, p[2]);
		p[3]=Math.max(nx, p[3]);
		
		if((cl!=ml||cr!=mr)&&(p[0]!=ml||p[1]!=mr)) {
			h=true;
		}
		if(((cu!=mu||cd!=md))&&(p[2]!=mu||p[3]!=md)) {
			v=true;
		}
		
		return p;
		
	}
}



class FastReader
{
	BufferedReader br;
	StringTokenizer st;

	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	public String next() 
	{
		if(st==null || !st.hasMoreElements())
		{
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	public int nextInt() 
	{
		return Integer.parseInt(next());
	}

	public long nextLong()
	{
		return Long.parseLong(next());
	}
}