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).
T = int(input())

w = [[-1, 0], [1, 0], [0, 1], [0, -1]]
mp = {'A':0, 'D':1, 'W':2, 'S':3}
while T > 0:
	T-=1
	s = input()
	l = [0]; r = [0];
	u = [0]; d = [0];

	for dir in s[::-1]:
		l.append(l[-1])
		r.append(r[-1])
		u.append(u[-1])
		d.append(d[-1])
		if dir == 'A':
			l[-1]+=1
			if r[-1] > 0: r[-1]-=1
		elif dir == 'D':
			r[-1]+=1
			if l[-1] > 0: l[-1]-=1
		elif dir == 'S':
			d[-1]+=1
			if u[-1] > 0: u[-1]-=1
		else:
			u[-1]+=1
			if d[-1] > 0: d[-1]-=1

	l = l[::-1]; r = r[::-1]; u = u[::-1]; d = d[::-1];

	x = 0; y = 0
	ml = 0; mr = 0; mu = 0; md = 0;

	ans = (l[0] + r[0] + 1) * (u[0] + d[0] + 1)
	for i in range(len(s)+1):
		mml=ml;mmr=mr;mmu=mu;mmd=md;
		for j in range(4):
			xx=x+w[j][0]
			yy=y+w[j][1]

			if xx<0: ml=max(ml,-xx)
			if xx>0: mr=max(mr,xx)
			if yy>0: mu=max(mu,yy)
			if yy<0: md=max(md,-yy)

			xx-=l[i]
			if xx<0: ml=max(ml,-xx)
			xx+=r[i]+l[i];
			if xx>0: mr=max(mr,xx)
			yy-=d[i]
			if yy<0: md=max(md,-yy)
			yy+=u[i]+d[i]
			if yy>0: mu=max(mu,yy)

			ans = min(ans, (ml+mr+1)*(mu+md+1))
			ml=mml;mr=mmr;mu=mmu;md=mmd;

		if i < len(s):
			x+=w[mp[s[i]]][0]
			y+=w[mp[s[i]]][1]
			if x<0: ml=max(ml,-x)
			if x>0: mr=max(mr,x)
			if y>0: mu=max(mu,y)
			if y<0: md=max(md,-y)

	print(ans)