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 = \text{DSAWWAW}$ then $Grid(s)$ is the $4 \times 3$ grid:  you can place the robot in the cell $(3, 2)$;  the robot performs the command 'D' and moves to $(3, 3)$;  the robot performs the command 'S' and moves to $(4, 3)$;  the robot performs the command 'A' and moves to $(4, 2)$;  the robot performs the command 'W' and moves to $(3, 2)$;  the robot performs the command 'W' and moves to $(2, 2)$;  the robot performs the command 'A' and moves to $(2, 1)$;  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 \le T \le 1000$) — the number of queries.

Next $T$ lines contain queries: one per line. This line contains single string $s$ ($1 \le |s| \le 2 \cdot 10^5$, $s_i \in \{\text{W}, \text{A}, \text{S}, \text{D}\}$) — the sequence of commands.

It's guaranteed that the total length of $s$ over all queries doesn't exceed $2 \cdot 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 $\text{DSAWW}\underline{D}\text{AW}$.

In second and third queries you can not decrease the area of $Grid(s)$.

Difficulty: HARD
Tags: String algorithms

Implementation

Complete search

Greedy algorithms

Dynamic programming

Mathematics

Data structures
Skill types: Dynamic programming

Data structures

Complete search

Greedy algorithms

Starter code:

Solutions:
for i in range(int(input())):
	s = input()
	(lm, rm, um, dm) = (0, 0, 0, 0)
	(xp, yp) = (0, 0)
	for ch in s:
		if ch == 'W':
			yp += 1
		elif ch == 'A':
			xp -= 1
		elif ch == 'S':
			yp -= 1
		else:
			xp += 1
		lm = min(lm, xp)
		rm = max(rm, xp)
		um = max(um, yp)
		dm = min(dm, yp)
	(xp, yp) = (0, 0)
	(lmfSet, rmfSet, umfSet, dmfSet) = (0, 0, 0, 0)
	if lm == 0:
		lml = 0
		lmf = 0
		lmfSet = 1
	if rm == 0:
		rml = 0
		rmf = 0
		rmfSet = 1
	if um == 0:
		uml = 0
		umf = 0
		umfSet = 1
	if dm == 0:
		dml = 0
		dmf = 0
		dmfSet = 1
	for (i, ch) in zip(list(range(1, len(s) + 1)), s):
		if ch == 'W':
			yp += 1
		elif ch == 'A':
			xp -= 1
		elif ch == 'S':
			yp -= 1
		else:
			xp += 1
		if xp == lm:
			lml = i
			if not lmfSet:
				lmf = i
				lmfSet = 1
		if xp == rm:
			rml = i
			if not rmfSet:
				rmf = i
				rmfSet = 1
		if yp == um:
			uml = i
			if not umfSet:
				umf = i
				umfSet = 1
		if yp == dm:
			dml = i
			if not dmfSet:
				dmf = i
				dmfSet = 1
	(canx, cany) = (0, 0)
	if dml + 1 < umf or uml + 1 < dmf:
		cany = 1
	if lml + 1 < rmf or rml + 1 < lmf:
		canx = 1
	if canx:
		if cany:
			print(min((um - dm) * (rm - lm + 1), (um - dm + 1) * (rm - lm)))
		else:
			print((rm - lm) * (um - dm + 1))
	elif cany:
		print((um - dm) * (rm - lm + 1))
	else:
		print((rm - lm + 1) * (um - dm + 1))


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	(fa, fd, fs, fw) = ([0], [0], [0], [0])
	(ba, bd, bs, bw) = ([0], [0], [0], [0])
	cur = [0, 0]
	for i in range(n):
		if s[i] == 'A':
			cur[0] -= 1
		elif s[i] == 'D':
			cur[0] += 1
		elif s[i] == 'S':
			cur[1] -= 1
		elif s[i] == 'W':
			cur[1] += 1
		fa.append(min(fa[-1], cur[0]))
		fd.append(max(fd[-1], cur[0]))
		fs.append(min(fs[-1], cur[1]))
		fw.append(max(fw[-1], cur[1]))
	h = fd[-1] - fa[-1]
	v = fw[-1] - fs[-1]
	area = (h + 1) * (v + 1)
	cur = [0, 0]
	for i in range(n - 1, -1, -1):
		if s[i] == 'D':
			cur[0] -= 1
		elif s[i] == 'A':
			cur[0] += 1
		elif s[i] == 'W':
			cur[1] -= 1
		elif s[i] == 'S':
			cur[1] += 1
		ba.append(min(ba[-1], cur[0]))
		bd.append(max(bd[-1], cur[0]))
		bs.append(min(bs[-1], cur[1]))
		bw.append(max(bw[-1], cur[1]))
	ba.reverse()
	bd.reverse()
	bs.reverse()
	bw.reverse()
	(hok, vok) = (False, False)
	for i in range(1, n):
		if fd[i] - fa[i] < h and abs(bd[i] - ba[i]) < h:
			hok = True
		if fw[i] - fs[i] < v and abs(bw[i] - bs[i]) < v:
			vok = True
	if hok:
		area = min(area, h * (v + 1))
	if vok:
		area = min(area, v * (h + 1))
	print(area)


def main():
	(hh, vv, r) = ([0], [0], [])
	f = {'W': (vv, -1), 'S': (vv, 1), 'A': (hh, -1), 'D': (hh, 1)}.get
	for _ in range(int(input())):
		del vv[1:], hh[1:], r[:]
		for (l, d) in map(f, input()):
			l.append(l[-1] + d)
		for l in (hh, vv):
			(mi, ma) = (min(l), max(l))
			(a, tmp) = (mi - 1, [])
			for b in filter((mi, ma).__contains__, l):
				if a != b:
					a = b
					tmp.append(a)
			ma -= mi - 1
			r.append(ma)
			if len(tmp) < 3 <= ma:
				ma -= 1
			r.append(ma)
		print(min((r[0] * r[3], r[1] * r[2])))
main()


t = int(input())
for c in range(t):
	s = input()
	up_max = down_max = right_max = left_max = 0
	first_up = last_up = first_down = last_down = first_left = last_left = first_right = last_right = 0
	current_x = current_y = 0
	horizontal_count = vertical_count = 0
	for i in range(len(s)):
		if s[i] == 'W':
			current_y += 1
			vertical_count += 1
			if current_y > up_max:
				up_max = current_y
				first_up = last_up = i + 1
			elif current_y == up_max:
				last_up = i + 1
		elif s[i] == 'S':
			current_y -= 1
			vertical_count += 1
			if current_y < down_max:
				down_max = current_y
				first_down = last_down = i + 1
			elif current_y == down_max:
				last_down = i + 1
		elif s[i] == 'D':
			current_x += 1
			horizontal_count += 1
			if current_x > right_max:
				right_max = current_x
				first_right = last_right = i + 1
			elif current_x == right_max:
				last_right = i + 1
		else:
			current_x -= 1
			horizontal_count += 1
			if current_x < left_max:
				left_max = current_x
				first_left = last_left = i + 1
			elif current_x == left_max:
				last_left = i + 1
	h = up_max - down_max + 1
	w = right_max - left_max + 1
	ans = h * w
	if vertical_count > 1 and last_up < first_down:
		ans = min(ans, (h - 1) * w)
	if vertical_count > 1 and last_down < first_up:
		ans = min(ans, (h - 1) * w)
	if horizontal_count > 1 and last_right < first_left:
		ans = min(ans, h * (w - 1))
	if horizontal_count > 1 and last_left < first_right:
		ans = min(ans, h * (w - 1))
	print(ans)


import sys
from collections import defaultdict
input = sys.stdin.readline
import math

def main():
	t = int(input())
	for _ in range(t):
		s = input().rstrip()
		a1 = []
		a2 = []
		ws = {'W': 1, 'S': -1}
		ad = {'A': 1, 'D': -1}
		for c in s:
			if c in ('W', 'S'):
				a1.append(ws[c])
			else:
				a2.append(ad[c])
		pref_a1 = [0] + a1.copy()
		pref_a2 = [0] + a2.copy()
		for i in range(1, len(pref_a1)):
			pref_a1[i] += pref_a1[i - 1]
		for i in range(1, len(pref_a2)):
			pref_a2[i] += pref_a2[i - 1]

		def canDecrease(a):
			_min = min(a)
			_max = max(a)
			_min_rindex = a.index(_min)
			for i in range(_min_rindex, len(a)):
				if a[i] == _min:
					_min_rindex = i
			_max_index = a.index(_max)
			if _max_index > _min_rindex:
				return True
			_max_rindex = a.index(_max)
			for i in range(_max_rindex, len(a)):
				if a[i] == _max:
					_max_rindex = i
			_min_index = a.index(_min)
			if _max_rindex < _min_index:
				return True
			return False
		x = max(pref_a1) - min(pref_a1)
		y = max(pref_a2) - min(pref_a2)
		res = (x + 1) * (y + 1)
		if x > 1 and canDecrease(pref_a1):
			res = min(res, x * (y + 1))
		if y > 1 and canDecrease(pref_a2):
			res = min(res, (x + 1) * y)
		print(res)

def __starting_point():
	main()
__starting_point()


for q in range(int(input())):
	data = input()
	mx = [0, 0, 0, 0]
	x = 0
	y = 0
	pos = [[-1], [-1], [-1], [-1]]
	for i in range(len(data)):
		d = data[i]
		if d == 'W':
			y += 1
			if y > mx[0]:
				mx[0] = y
				pos[0] = []
		elif d == 'S':
			y -= 1
			if y < mx[2]:
				mx[2] = y
				pos[2] = []
		elif d == 'A':
			x -= 1
			if x < mx[1]:
				mx[1] = x
				pos[1] = []
		else:
			x += 1
			if x > mx[3]:
				mx[3] = x
				pos[3] = []
		if x == mx[3]:
			pos[3].append(i)
		if x == mx[1]:
			pos[1].append(i)
		if y == mx[0]:
			pos[0].append(i)
		if y == mx[2]:
			pos[2].append(i)
	wid = mx[3] - mx[1] + 1
	hei = mx[0] - mx[2] + 1
	ans = wid * hei
	if pos[3][0] > pos[1][-1] + 1 or pos[1][0] > pos[3][-1] + 1:
		ans -= hei
	if pos[0][0] > pos[2][-1] + 1 or pos[2][0] > pos[0][-1] + 1:
		ans = min((hei - 1) * wid, ans)
	print(ans)


t = int(input())
for _ in range(0, t):
	a = list(input())
	nowx = 0
	nowy = 0
	maxx = 0
	minx = 0
	maxy = 0
	miny = 0
	tmaxx = 0
	tminx = 0
	tmaxy = 0
	tminy = 0
	highw = 0
	highs = 0
	widthd = 0
	widtha = 0
	for i in range(0, len(a)):
		if a[i] == 'W':
			nowy += 1
			if nowy >= maxy:
				maxy = nowy
				tmaxy = i
		elif a[i] == 'S':
			nowy -= 1
			if nowy <= miny:
				miny = nowy
				tminy = i
		elif a[i] == 'D':
			nowx += 1
			if nowx >= maxx:
				maxx = nowx
				tmaxx = i
		elif a[i] == 'A':
			nowx -= 1
			if nowx <= minx:
				minx = nowx
				tminx = i
		highw = max(highw, nowy - miny)
		highs = max(highs, maxy - nowy)
		widthd = max(widthd, nowx - minx)
		widtha = max(widtha, maxx - nowx)
	y1 = max(highw, highs)
	y2 = max(highw != 0 or highs != 0, y1 - (highw != highs))
	x1 = max(widthd, widtha)
	x2 = max(widthd != 0 or widtha != 0, x1 - (widthd != widtha))
	print(min((y1 + 1) * (x2 + 1), (1 + y2) * (x1 + 1)))


import sys
input = sys.stdin.readline
Q = int(input())
for testcases in range(Q):
	S = input().strip()
	X = Y = 0
	MAXX = MINX = MAXY = MINY = 0
	for s in S:
		if s == 'D':
			X += 1
			MAXX = max(MAXX, X)
		elif s == 'A':
			X -= 1
			MINX = min(MINX, X)
		elif s == 'W':
			Y += 1
			MAXY = max(MAXY, Y)
		else:
			Y -= 1
			MINY = min(MINY, Y)
	MAXXLIST = []
	MINXLIST = []
	MAXYLIST = []
	MINYLIST = []
	if MAXX == 0:
		MAXXLIST.append(0)
	if MAXY == 0:
		MAXYLIST.append(0)
	if MINX == 0:
		MINXLIST.append(0)
	if MINY == 0:
		MINYLIST.append(0)
	X = Y = 0
	for i in range(len(S)):
		s = S[i]
		if s == 'D':
			X += 1
			if X == MAXX:
				MAXXLIST.append(i + 1)
		elif s == 'A':
			X -= 1
			if X == MINX:
				MINXLIST.append(i + 1)
		elif s == 'W':
			Y += 1
			if Y == MAXY:
				MAXYLIST.append(i + 1)
		else:
			Y -= 1
			if Y == MINY:
				MINYLIST.append(i + 1)
	ANS = (MAXX - MINX + 1) * (MAXY - MINY + 1)
	if MAXX - MINX > 1:
		if MAXXLIST[0] > MINXLIST[-1] or MINXLIST[0] > MAXXLIST[-1]:
			ANS = min(ANS, (MAXX - MINX) * (MAXY - MINY + 1))
	if MAXY - MINY > 1:
		if MAXYLIST[0] > MINYLIST[-1] or MINYLIST[0] > MAXYLIST[-1]:
			ANS = min(ANS, (MAXX - MINX + 1) * (MAXY - MINY))
	print(ANS)


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
uu = t

def sol(a):
	n = len(a)
	sm = [a[-1]]
	smi = [a[-1]]
	for i in range(n - 2, -1, -1):
		sm.append(max(sm[-1], a[i]))
		smi.append(min(smi[-1], a[i]))
	sm = sm[::-1]
	smi = smi[::-1]
	maxi = -10 ** 18
	mini = 10 ** 18
	ans = max(a) - min(a) + 1
	for i in range(n - 1):
		for j in range(-1, 2):
			cm = max(maxi, sm[i] + j)
			cmi = min(mini, smi[i] + j)
			ans = min(ans, cm - cmi + 1)
		maxi = max(maxi, a[i])
		mini = min(mini, a[i])
	return ans
while t > 0:
	t -= 1
	s = si()
	n = len(s)
	for i in range(n):
		if s[i] == 'W':
			s[i] = 'U'
		elif s[i] == 'A':
			s[i] = 'L'
		elif s[i] == 'S':
			s[i] = 'D'
		else:
			s[i] = 'R'
	h = v = 0
	a = [0]
	b = [0]
	for i in s:
		(pv, ph) = (v, h)
		if i == 'L':
			h -= 1
		elif i == 'R':
			h += 1
		elif i == 'U':
			v += 1
		else:
			v -= 1
		if ph != h:
			a.append(h)
		if pv != v:
			b.append(v)
	print(min(sol(a) * (max(b) - min(b) + 1), sol(b) * (max(a) - min(a) + 1)))


for _ in range(int(input())):
	s = input()
	ar = ['AD', 'WS']
	nr = [[], []]
	for e in s:
		if e in ar[0]:
			nr[0].append(e)
		else:
			nr[1].append(e)
	(b, c) = ([float('inf')] * 2, [float('inf')] * 2)
	for i in range(2):
		sm = [0]
		for el in nr[i]:
			sm += [sm[-1] + (1 if el == ar[i][0] else -1)]
		for _ in range(2):
			f = sm.index(min(sm))
			l = len(sm) - 1 - sm[::-1].index(max(sm))
			bse = sm[l] - sm[f] + 1
			bst = bse
			if bse >= 3 and l < f:
				bst -= 1
			b[i] = min(b[i], bse)
			c[i] = min(c[i], bst)
			for j in range(len(sm)):
				sm[j] *= -1
	print(min(b[0] * c[1], b[1] * c[0]))


t = int(input())

def possible(presum):
	l = len(presum)
	lastmax = -1
	firstmin = l
	mx = max(presum)
	mn = min(presum)
	for i in range(l):
		if mx == presum[i]:
			lastmax = max(lastmax, i)
		if mn == presum[i]:
			firstmin = min(i, firstmin)
	if lastmax < firstmin:
		return True
	return False
for i in range(t):
	s = input()
	l1 = [0]
	l2 = [0]
	for i in s:
		if i == 'S':
			l1.append(l1[-1] - 1)
		elif i == 'W':
			l1.append(l1[-1] + 1)
		elif i == 'D':
			l2.append(l2[-1] + 1)
		else:
			l2.append(l2[-1] - 1)
	length = max(l1) - min(l1) + 1
	breadth = max(l2) - min(l2) + 1
	ans = length * breadth
	if length > 2 and possible(l1):
		ans = min(ans, (length - 1) * breadth)
	for i in range(len(l1)):
		l1[i] *= -1
	if length > 2 and possible(l1):
		ans = min(ans, (length - 1) * breadth)
	if breadth > 2 and possible(l2):
		ans = min(ans, length * (breadth - 1))
	for i in range(len(l2)):
		l2[i] *= -1
	if breadth > 2 and possible(l2):
		ans = min(ans, length * (breadth - 1))
	print(ans)


def solve():
	i = 0
	j = 0
	imax = imin = 0
	jmax = jmin = 0
	fjmin = ljmin = fjmax = ljmax = fimax = limax = fimin = limin = -1
	for (ind, e) in enumerate(input()):
		if e == 'W':
			i += 1
			if i > imax:
				imax = i
				fimax = ind
				limax = ind
		elif e == 'S':
			i -= 1
			if i < imin:
				imin = i
				fimin = ind
				limin = ind
		elif e == 'A':
			j -= 1
			if j < jmin:
				jmin = j
				fjmin = ind
				ljmin = ind
		elif e == 'D':
			j += 1
			if j > jmax:
				jmax = j
				fjmax = ind
				ljmax = ind
		if j == jmin:
			ljmin = ind
		if j == jmax:
			ljmax = ind
		if i == imin:
			limin = ind
		if i == imax:
			limax = ind
	ans = 0
	if fjmax > ljmin + 1 or fjmin > ljmax + 1:
		ans = imax - imin + 1
	if fimax > limin + 1 or fimin > limax + 1:
		ans = max(ans, jmax - jmin + 1)
	print((imax - imin + 1) * (jmax - jmin + 1) - ans)
for _ in range(int(input())):
	solve()


T = int(input())
for _ in range(T):
	cmd = input()
	(mostL, mostR, mostB, mostT) = (0, 0, 0, 0)
	(mostLs, mostRs, mostBs, mostTs) = ([0], [0], [0], [0])
	(x, y) = (0, 0)
	i = 0
	for c in cmd:
		i += 1
		if c == 'W':
			y += 1
			if y > mostT:
				mostT = y
				mostTs = [i]
			elif y == mostT:
				mostTs.append(i)
		elif c == 'S':
			y -= 1
			if y < mostB:
				mostB = y
				mostBs = [i]
			elif y == mostB:
				mostBs.append(i)
		elif c == 'A':
			x -= 1
			if x < mostL:
				mostL = x
				mostLs = [i]
			elif x == mostL:
				mostLs.append(i)
		elif c == 'D':
			x += 1
			if x > mostR:
				mostR = x
				mostRs = [i]
			elif x == mostR:
				mostRs.append(i)
	LR = mostR - mostL + 1
	if LR >= 3:
		(firstL, lastL) = (mostLs[0], mostLs[-1])
		(firstR, lastR) = (mostRs[0], mostRs[-1])
		cross = lastR > firstL and lastL > firstR
		LR_extra = not cross
	else:
		LR_extra = False
	BT = mostT - mostB + 1
	if BT >= 3:
		(firstB, lastB) = (mostBs[0], mostBs[-1])
		(firstT, lastT) = (mostTs[0], mostTs[-1])
		cross = lastB > firstT and lastT > firstB
		BT_extra = not cross
	else:
		BT_extra = False
	if LR_extra and BT_extra:
		area = min((LR - 1) * BT, LR * (BT - 1))
	elif LR_extra:
		area = (LR - 1) * BT
	elif BT_extra:
		area = LR * (BT - 1)
	else:
		area = LR * BT
	print(area)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input()
	(l, r, u, d, fl, fr, fu, fd, x, y) = [0] * 10
	for i in range(len(s)):
		if s[i] == 'W':
			y += 1
			if y > u:
				u = y
				fd = 0
				fu = 1
			if y == u:
				fu = 1
		elif s[i] == 'A':
			x -= 1
			if x < l:
				l = x
				fl = 1
				fr = 0
			if x == l:
				fl = 1
		elif s[i] == 'S':
			y -= 1
			if y < d:
				d = y
				fd = 1
				fu = 0
			if y == d:
				fd = 1
		elif s[i] == 'D':
			x += 1
			if x > r:
				r = x
				fr = 1
				fl = 0
			if x == r:
				fr = 1
	(x, y) = (r - l + 1, u - d + 1)
	(s, k) = (x * y, x * y)
	if x > 2 and (not fl * fr):
		s = k - y
	if y > 2 and (not fu * fd) and (k - x < s):
		s = k - x
	print(s)


def Grid(S):
	xmin = [0, [-1]]
	xmax = [0, [-1]]
	ymin = [0, [-1]]
	ymax = [0, [-1]]
	y_s = 0
	x_s = 0
	n = len(S)
	for i in range(n):
		c = S[i]
		if c == 'W':
			y_s += 1
		elif c == 'S':
			y_s -= 1
		elif c == 'A':
			x_s -= 1
		else:
			x_s += 1
		if x_s == xmin[0]:
			xmin[1].append(i)
		elif x_s < xmin[0]:
			xmin = [x_s, [i]]
		if x_s == xmax[0]:
			xmax[1].append(i)
		elif x_s > xmax[0]:
			xmax = [x_s, [i]]
		if y_s == ymin[0]:
			ymin[1].append(i)
		elif y_s < ymin[0]:
			ymin = [y_s, [i]]
		if y_s == ymax[0]:
			ymax[1].append(i)
		elif y_s > ymax[0]:
			ymax = [y_s, [i]]
	return [xmin, xmax, ymin, ymax]

def process(S):
	(A, B, C, D) = Grid(S)
	(a, al) = A
	(b, bl) = B
	(c, cl) = C
	(d, dl) = D
	answer = (b - a + 1) * (d - c + 1)
	if bl[-1] < al[0] - 1 or al[-1] < bl[0] - 1:
		answer = min(answer, (b - a) * (d - c + 1))
	if dl[-1] < cl[0] - 1 or cl[-1] < dl[0] - 1:
		answer = min(answer, (b - a + 1) * (d - c))
	return answer
t = int(input())
for i in range(t):
	S = input()
	print(process(S))


t = int(input())
for _ in range(t):
	ss = input()
	minx = 0
	fminxpos = -1
	lminxpos = -1
	maxx = 0
	fmaxxpos = -1
	lmaxxpos = -1
	miny = 0
	fminypos = -1
	lminypos = -1
	maxy = 0
	fmaxypos = -1
	lmaxypos = -1
	x = 0
	y = 0
	for (i, s) in enumerate(ss):
		if s == 'W':
			y += 1
			if y > maxy:
				maxy = y
				fmaxypos = i
			if y == maxy:
				lmaxypos = i
		elif s == 'S':
			y -= 1
			if y < miny:
				miny = y
				fminypos = i
			if y == miny:
				lminypos = i
		elif s == 'D':
			lastd = i
			x += 1
			if x > maxx:
				maxx = x
				fmaxxpos = i
			if x == maxx:
				lmaxxpos = i
		elif s == 'A':
			lasta = i
			x -= 1
			if x < minx:
				minx = x
				fminxpos = i
			if x == minx:
				lminxpos = i
	xsize = maxx - minx + 1
	ysize = maxy - miny + 1
	if xsize > 2 and (fmaxxpos > lminxpos or fminxpos > lmaxxpos):
		xmin = xsize - 1
	else:
		xmin = xsize
	if ysize > 2 and (fmaxypos > lminypos or fminypos > lmaxypos):
		ymin = ysize - 1
	else:
		ymin = ysize
	print(min(xmin * ysize, xsize * ymin))


from sys import setrecursionlimit as SRL, stdin
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
n = int(input())
while n:
	s = map(str, rd().strip())
	l = 0
	pl = 1
	r = 0
	pr = 1
	u = 0
	pu = 1
	b = 0
	pb = 1
	curx = 0
	cury = 0
	for x in s:
		if x == 'S':
			cury -= 1
			if cury < b:
				b = cury
				if u - b > 1:
					pu = 0
			elif cury == b:
				pb = 1
		elif x == 'W':
			cury += 1
			if cury > u:
				u = cury
				if u - b > 1:
					pb = 0
			elif cury == u:
				pu = 1
		elif x == 'A':
			curx -= 1
			if curx < l:
				l = curx
				if r - l > 1:
					pr = 0
			elif curx == l:
				pl = 1
		elif x == 'D':
			curx += 1
			if curx > r:
				r = curx
				if r - l > 1:
					pl = 0
			elif curx == r:
				pr = 1
	ans = (r - l + 1) * (u - b + 1)
	if not pl or not pr:
		ans = min(ans, (r - l) * (u - b + 1))
	if not pb or not pu:
		ans = min(ans, (r - l + 1) * (u - b))
	print(ans)
	n -= 1


def read_int():
	return int(input())

def read_ints():
	return map(int, input().split(' '))
t = read_int()
INF = int(10000000.0)
for case_num in range(t):
	s = input()
	x = 0
	y = 0
	xlist = [0]
	ylist = [0]
	for c in s:
		if c == 'W':
			y += 1
		elif c == 'S':
			y -= 1
		elif c == 'A':
			x -= 1
		else:
			x += 1
		xlist.append(x)
		ylist.append(y)
	n = len(s)
	l = [0]
	r = [0]
	u = [0]
	d = [0]
	for i in range(1, n + 1):
		l.append(min(l[-1], xlist[i]))
		r.append(max(r[-1], xlist[i]))
		u.append(max(u[-1], ylist[i]))
		d.append(min(d[-1], ylist[i]))
	lr = [xlist[n]]
	rr = [xlist[n]]
	ur = [ylist[n]]
	dr = [ylist[n]]
	for i in range(1, n + 1):
		lr.append(min(lr[-1], xlist[n - i]))
		rr.append(max(rr[-1], xlist[n - i]))
		ur.append(max(ur[-1], ylist[n - i]))
		dr.append(min(dr[-1], ylist[n - i]))
	ans = INF * INF
	coeff = [[-1, 0], [1, 0], [0, -1], [0, 1]]
	for k in range(4):
		for i in range(n):
			nl = min(l[i], lr[n - i] + coeff[k][0])
			nr = max(r[i], rr[n - i] + coeff[k][0])
			nu = max(u[i], ur[n - i] + coeff[k][1])
			nd = min(d[i], dr[n - i] + coeff[k][1])
			area = (nr - nl + 1) * (nu - nd + 1)
			ans = min(ans, area)
	print(ans)


n = int(input())

def area(width, height):
	return (width + 1) * (height + 1)

def calcul(s1, c, s2):
	(maxx, maxy, minx, miny) = (0, 0, 0, 0)
	(x, y) = (0, 0)
	for k in range(len(s1)):
		if s1[k] == 'W':
			y += 1
		if s1[k] == 'S':
			y -= 1
		if s1[k] == 'A':
			x -= 1
		if s1[k] == 'D':
			x += 1
		maxx = max(maxx, x)
		minx = min(minx, x)
		maxy = max(maxy, y)
		miny = min(miny, y)
	if c == 'W':
		y += 1
	elif c == 'S':
		y -= 1
	elif c == 'A':
		x -= 1
	elif c == 'D':
		x += 1
	else:
		print(c, 'ok')
	maxx = max(maxx, x)
	minx = min(minx, x)
	maxy = max(maxy, y)
	miny = min(miny, y)
	for k in range(len(s2)):
		if s2[k] == 'W':
			y += 1
		if s2[k] == 'S':
			y -= 1
		if s2[k] == 'A':
			x -= 1
		if s2[k] == 'D':
			x += 1
		maxx = max(maxx, x)
		minx = min(minx, x)
		maxy = max(maxy, y)
		miny = min(miny, y)
	diffx = maxx - minx
	diffy = maxy - miny
	tmp = area(diffx, diffy)
	return tmp

def pre_calcul(s, moment, pre_avant, date_debut):
	(x, y, maxx, minx, maxy, miny) = pre_avant
	for k in range(date_debut, moment):
		if s[k] == 'W':
			y += 1
		if s[k] == 'S':
			y -= 1
		if s[k] == 'A':
			x -= 1
		if s[k] == 'D':
			x += 1
		maxx = max(maxx, x)
		minx = min(minx, x)
		maxy = max(maxy, y)
		miny = min(miny, y)
	return (x, y, maxx, minx, maxy, miny)

def calcul2(s, c, moment, precalcul):
	(x, y, maxx, minx, maxy, miny) = precalcul
	if c == 'W':
		y += 1
	elif c == 'S':
		y -= 1
	elif c == 'A':
		x -= 1
	elif c == 'D':
		x += 1
	else:
		print(c, 'ok')
	maxx = max(maxx, x)
	minx = min(minx, x)
	maxy = max(maxy, y)
	miny = min(miny, y)
	for k in range(moment, len(s)):
		if s[k] == 'W':
			y += 1
		if s[k] == 'S':
			y -= 1
		if s[k] == 'A':
			x -= 1
		if s[k] == 'D':
			x += 1
		maxx = max(maxx, x)
		minx = min(minx, x)
		maxy = max(maxy, y)
		miny = min(miny, y)
	diffx = maxx - minx
	diffy = maxy - miny
	tmp = area(diffx, diffy)
	return tmp
for _ in range(n):
	s = input()
	(maxx, maxy, minx, miny) = (0, 0, 0, 0)
	(x, y) = (0, 0)
	(momentminx, momentmaxx, momentminy, momentmaxy) = (-1, -1, -1, -1)
	for k in range(len(s)):
		if s[k] == 'W':
			y += 1
		if s[k] == 'S':
			y -= 1
		if s[k] == 'A':
			x -= 1
		if s[k] == 'D':
			x += 1
		if x > maxx:
			momentmaxx = k
		if y > maxy:
			momentmaxy = k
		if x < minx:
			momentminx = k
		if y < miny:
			momentminy = k
		maxx = max(maxx, x)
		minx = min(minx, x)
		maxy = max(maxy, y)
		miny = min(miny, y)
	diffx = maxx - minx
	diffy = maxy - miny
	tmp = 999999999999999999999999999999999999
	l = [momentmaxx, momentmaxy, momentminx, momentminy]
	l = list(set(l))
	l = [i for i in l if i != -1]
	l.sort()
	if l != []:
		precalcul = pre_calcul(s, l[0], (0, 0, 0, 0, 0, 0), 0)
		avant = l[0]
		for moment in l:
			precalcul = pre_calcul(s, moment, precalcul, avant)
			avant = moment
			tmp = min(tmp, calcul2(s, 'W', moment, precalcul))
			tmp = min(tmp, calcul2(s, 'S', moment, precalcul))
			tmp = min(tmp, calcul2(s, 'A', moment, precalcul))
			tmp = min(tmp, calcul2(s, 'D', moment, precalcul))
	print(tmp)


import sys

def work(c, c1, s):
	(maxlast, maxfirst, minlast, minfirst) = (0, 0, 0, 0)
	max = 0
	min = 0
	y = 0
	for i in range(len(s)):
		if s[i] == c:
			y += 1
		elif s[i] == c1:
			y -= 1
		if max < y:
			(maxfirst, maxlast) = (i, i)
			max = y
		elif max == y:
			maxlast = i
		if y < min:
			(minlast, minfirst) = (i, i)
			min = y
		elif min == y:
			minlast = i
	flag = 0
	if (maxlast < minfirst or maxfirst > minlast) and max - min > 1:
		flag = 1
	return (max - min + 1, flag)
count = 0
for line in sys.stdin:
	if count == 0:
		n = int(line.strip().split(' ')[0])
		count += 1
		continue
	s = line.strip()
	(flag, flag1) = (0, 0)
	(n, flag) = work('W', 'S', s)
	(m, flag1) = work('A', 'D', s)
	res = n * m
	if flag1 and flag:
		res = min(n * (m - 1), m * (n - 1))
	elif flag:
		res = m * (n - 1)
	elif flag1:
		res = (m - 1) * n
	print(res)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	s = input()
	(x, y) = (0, 0)
	(minx, miny) = (0, 0)
	(maxx, maxy) = (0, 0)
	for i in s:
		if i == 'W':
			y += 1
		if i == 'S':
			y -= 1
		if i == 'D':
			x += 1
		if i == 'A':
			x -= 1
		minx = min(minx, x)
		maxx = max(maxx, x)
		miny = min(miny, y)
		maxy = max(maxy, y)
	ans = (maxx - minx + 1) * (maxy - miny + 1)
	(x, y) = (0, 0)
	(m1, m2, m3, m4) = (0, 0, 0, 0)
	taken = False
	for i in s:
		if i == 'W':
			if y + 1 == maxy and (not taken):
				taken = True
				m3 = min(m3, y - 1)
				m4 = max(m4, y - 1)
			else:
				y += 1
		if i == 'S':
			y -= 1
		if i == 'D':
			x += 1
		if i == 'A':
			x -= 1
		m1 = min(m1, x)
		m2 = max(m2, x)
		m3 = min(m3, y)
		m4 = max(m4, y)
	ans = min(ans, (m2 - m1 + 1) * (m4 - m3 + 1))
	(x, y) = (0, 0)
	(m1, m2, m3, m4) = (0, 0, 0, 0)
	taken = False
	for i in s:
		if i == 'S':
			if y - 1 == miny and (not taken):
				taken = True
				m3 = min(m3, y + 1)
				m4 = max(m4, y + 1)
			else:
				y -= 1
		if i == 'W':
			y += 1
		if i == 'D':
			x += 1
		if i == 'A':
			x -= 1
		m1 = min(m1, x)
		m2 = max(m2, x)
		m3 = min(m3, y)
		m4 = max(m4, y)
	ans = min(ans, (m2 - m1 + 1) * (m4 - m3 + 1))
	(x, y) = (0, 0)
	(m1, m2, m3, m4) = (0, 0, 0, 0)
	taken = False
	for i in s:
		if i == 'D':
			if x + 1 == maxx and (not taken):
				taken = True
				m1 = min(m1, x - 1)
				m2 = max(m2, x - 1)
			else:
				x += 1
		if i == 'S':
			y -= 1
		if i == 'W':
			y += 1
		if i == 'A':
			x -= 1
		m1 = min(m1, x)
		m2 = max(m2, x)
		m3 = min(m3, y)
		m4 = max(m4, y)
	ans = min(ans, (m2 - m1 + 1) * (m4 - m3 + 1))
	(x, y) = (0, 0)
	(m1, m2, m3, m4) = (0, 0, 0, 0)
	taken = False
	for i in s:
		if i == 'A':
			if x - 1 == minx and (not taken):
				taken = True
				m1 = min(m1, x + 1)
				m2 = max(m2, x + 1)
			else:
				x -= 1
		if i == 'S':
			y -= 1
		if i == 'D':
			x += 1
		if i == 'W':
			y += 1
		m1 = min(m1, x)
		m2 = max(m2, x)
		m3 = min(m3, y)
		m4 = max(m4, y)
	ans = min(ans, (m2 - m1 + 1) * (m4 - m3 + 1))
	print(ans)


def main():
	(h, v) = hv = ([0], [0])
	f = {'W': (v, -1), 'S': (v, 1), 'A': (h, -1), 'D': (h, 1)}.get
	for _ in range(int(input())):
		del h[1:], v[1:]
		for (l, d) in map(f, input()):
			l.append(l[-1] + d)
		x = y = 1
		for l in hv:
			(lh, a, n) = ((min(l), max(l)), 200001, 0)
			for b in filter(lh.__contains__, l):
				if a != b:
					a = b
					n += 1
			le = lh[1] - lh[0] + 1
			(x, y) = (y * le, x * (le - (n < 3 <= le)))
		print(x if x < y else y)
main()


T = int(input())
for _ in range(T):
	s = input()
	cleft = cup = cdown = cright = 0
	left = up = down = right = 0
	fleft = lleft = 0
	fright = lright = 0
	fup = lup = 0
	fdown = ldown = 0
	x = y = 0
	for (i, c) in enumerate(s):
		if c == 'W':
			y -= 1
			cup += 1
		elif c == 'S':
			y += 1
			cdown += 1
		elif c == 'A':
			x -= 1
			cleft += 1
		elif c == 'D':
			x += 1
			cright += 1
		if x == left:
			lleft = i
		if x == right:
			lright = i
		if y == down:
			ldown = i
		if y == up:
			lup = i
		if x < left:
			left = x
			fleft = i
			lleft = i
		if x > right:
			right = x
			fright = i
			lright = i
		if y < up:
			up = y
			fup = i
			lup = i
		if y > down:
			down = y
			fdown = i
			ldown = i
	width = right - left + 1
	height = down - up + 1
	best = width * height
	if height > 2:
		if ldown < fup or lup < fdown:
			best = min(best, width * (height - 1))
	if width > 2:
		if lleft < fright or lright < fleft:
			best = min(best, (width - 1) * height)
	print(best)


INF = 100000000000.0
move = {'W': (0, 1), 'A': (-1, 0), 'S': (0, -1), 'D': (1, 0)}

def getExtremes(positions):
	(minX, minY, maxX, maxY) = ([positions[0][0]], [positions[0][1]], [positions[0][0]], [positions[0][1]])
	for p in positions[1:]:
		minX.append(min(minX[-1], p[0]))
		minY.append(min(minY[-1], p[1]))
		maxX.append(max(maxX[-1], p[0]))
		maxY.append(max(maxY[-1], p[1]))
	return (minX, minY, maxX, maxY)
t = int(input())
while t > 0:
	t -= 1
	s = input()
	(x, y) = (0, 0)
	positions = [(0, 0)]
	for c in s:
		(x, y) = (x + move[c][0], y + move[c][1])
		positions.append((x, y))
	(minXBeg, minYBeg, maxXBeg, maxYBeg) = getExtremes(positions)
	positions.reverse()
	(minXEnd, minYEnd, maxXEnd, maxYEnd) = getExtremes(positions)
	minXEnd.reverse()
	minYEnd.reverse()
	maxXEnd.reverse()
	maxYEnd.reverse()
	positions.reverse()
	ans = INF
	for i in range(len(s)):
		for c in move:
			minX = min(minXBeg[i], positions[i][0] + move[c][0], minXEnd[i + 1] + move[c][0])
			maxX = max(maxXBeg[i], positions[i][0] + move[c][0], maxXEnd[i + 1] + move[c][0])
			minY = min(minYBeg[i], positions[i][1] + move[c][1], minYEnd[i + 1] + move[c][1])
			maxY = max(maxYBeg[i], positions[i][1] + move[c][1], maxYEnd[i + 1] + move[c][1])
			area = (maxX - minX + 1) * (maxY - minY + 1)
			ans = min(ans, area)
	print(ans)


import sys
input = sys.stdin.readline
Q = int(input())
Query = [list(input().rstrip()) for _ in range(Q)]
for S in Query:
	L = len(S)
	T = [(0, 0)]
	for s in S:
		(x, y) = T[-1]
		if s == 'W':
			T.append((x, y + 1))
		elif s == 'S':
			T.append((x, y - 1))
		elif s == 'A':
			T.append((x - 1, y))
		else:
			T.append((x + 1, y))
	dp1 = [[0, 0, 0, 0] for _ in range(L + 1)]
	for (i, (x, y)) in enumerate(T):
		if i == 0:
			continue
		dp1[i][0] = max(y, dp1[i - 1][0])
		dp1[i][1] = min(y, dp1[i - 1][1])
		dp1[i][2] = min(x, dp1[i - 1][2])
		dp1[i][3] = max(x, dp1[i - 1][3])
	(lx, ly) = T[-1]
	dp2 = [[ly, ly, lx, lx] for _ in range(L + 1)]
	for i in reversed(range(L)):
		(x, y) = T[i]
		dp2[i][0] = max(y, dp2[i + 1][0])
		dp2[i][1] = min(y, dp2[i + 1][1])
		dp2[i][2] = min(x, dp2[i + 1][2])
		dp2[i][3] = max(x, dp2[i + 1][3])
	(Y, X) = (dp1[L][0] - dp1[L][1] + 1, dp1[L][3] - dp1[L][2] + 1)
	ans = 0
	for i in range(L):
		if dp1[i][0] < dp2[i][0] and dp1[i][1] < dp2[i][1]:
			ans = max(ans, X)
		if dp1[i][0] > dp2[i][0] and dp1[i][1] > dp2[i][1]:
			ans = max(ans, X)
		if dp1[i][2] < dp2[i][2] and dp1[i][3] < dp2[i][3]:
			ans = max(ans, Y)
		if dp1[i][2] > dp2[i][2] and dp1[i][3] > dp2[i][3]:
			ans = max(ans, Y)
	print(X * Y - ans)


q = int(input())
for _ in range(q):
	d = [x for x in list(input())]
	(x, y) = (0, 0)
	(minX, maxX, minY, maxY) = (0, 0, 0, 0)
	(allowW, allowS, allowA, allowD) = (True, True, True, True)
	for v in d:
		if v == 'W':
			y += 1
			if y > maxY:
				maxY = y
				allowS = True
				allowW = False
			elif y == maxY:
				allowW = False
		elif v == 'S':
			y -= 1
			if y < minY:
				minY = y
				allowW = True
				allowS = False
			elif y == minY:
				allowS = False
		elif v == 'A':
			x -= 1
			if x < minX:
				minX = x
				allowA = False
				allowD = True
			elif x == minX:
				allowA = False
		else:
			x += 1
			if x > maxX:
				maxX = x
				allowA = True
				allowD = False
			elif x == maxX:
				allowD = False
	val = (maxX - minX + 1) * (maxY - minY + 1)
	if maxX - minX > 1 and (allowD or allowA):
		val = min(val, (maxX - minX) * (maxY - minY + 1))
	if maxY - minY > 1 and (allowW or allowS):
		val = min(val, (maxX - minX + 1) * (maxY - minY))
	print(val)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input().strip()
	ans = 10 ** 15
	suffix_change = [0] * len(s)
	mx_x = mn_x = mx_y = mn_y = 0
	curr_x = curr_y = 0
	for j in range(len(s) - 1, -1, -1):
		i = s[j]
		if i == 'W':
			curr_y -= 1
		elif i == 'A':
			curr_x += 1
		elif i == 'S':
			curr_y += 1
		elif i == 'D':
			curr_x -= 1
		mx_x = max(mx_x, curr_x)
		mn_x = min(mn_x, curr_x)
		mx_y = max(mx_y, curr_y)
		mn_y = min(mn_y, curr_y)
		suffix_change[j] = [mx_x, mn_x, mx_y, mn_y]
	final_x = -curr_x
	final_y = -curr_y
	ans = (mx_x - mn_x + 1) * (mx_y - mn_y + 1)
	mx_x = mn_x = mx_y = mn_y = 0
	curr_x = curr_y = 0
	changes = [[0, 1], [0, -1], [1, 0], [-1, 0]]
	for j in range(len(s)):
		i = s[j]
		if i == 'W':
			curr_y += 1
		elif i == 'A':
			curr_x -= 1
		elif i == 'S':
			curr_y -= 1
		elif i == 'D':
			curr_x += 1
		mx_x = max(mx_x, curr_x)
		mn_x = min(mn_x, curr_x)
		mx_y = max(mx_y, curr_y)
		mn_y = min(mn_y, curr_y)
		if j < len(s) - 1:
			(mx_x2, mn_x2, mx_y2, mn_y2) = suffix_change[j + 1]
			mx_x2 += final_x
			mn_x2 += final_x
			mx_y2 += final_y
			mn_y2 += final_y
			for change in changes:
				ans = min(ans, (max(mx_x, mx_x2 + change[0]) - min(mn_x, mn_x2 + change[0]) + 1) * (max(mx_y, mx_y2 + change[1]) - min(mn_y, mn_y2 + change[1]) + 1))
	print(ans)


from sys import stdin
from sys import setrecursionlimit as SRL
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
t = int(input())
while t:
	s = str(rd().strip())
	s = '0' + s + '0'
	g = s[::-1]
	posx = [0] * len(s)
	posy = [0] * len(s)
	l = [0] * len(s)
	r = [0] * len(s)
	tp = [0] * len(s)
	b = [0] * len(s)
	rposx = [0] * len(s)
	rposy = [0] * len(s)
	rl = [0] * len(s)
	rr = [0] * len(s)
	rt = [0] * len(s)
	rb = [0] * len(s)
	posx[0] = posy[0] = l[0] = r[0] = tp[0] = b[0] = 2 * 10 ** 5 + 50
	for i in range(1, len(s) - 1):
		if s[i] == 'W':
			posy[i] = posy[i - 1] + 1
		elif s[i] == 'S':
			posy[i] = posy[i - 1] - 1
		elif s[i] == 'A':
			posx[i] = posx[i - 1] - 1
		elif s[i] == 'D':
			posx[i] = posx[i - 1] + 1
		if not posx[i]:
			posx[i] = posx[i - 1]
		if not posy[i]:
			posy[i] = posy[i - 1]
		l[i] = min(l[i - 1], posx[i])
		r[i] = max(r[i - 1], posx[i])
		b[i] = min(b[i - 1], posy[i])
		tp[i] = max(tp[i - 1], posy[i])
	rt[0] = rb[0] = rposy[0] = posy[len(s) - 2]
	rl[0] = rr[0] = rposx[0] = posx[len(s) - 2]
	for i in range(1, len(g) - 1):
		if g[i] == 'W':
			rposy[i] = rposy[i - 1] - 1
		elif g[i] == 'S':
			rposy[i] = rposy[i - 1] + 1
		elif g[i] == 'A':
			rposx[i] = rposx[i - 1] + 1
		elif g[i] == 'D':
			rposx[i] = rposx[i - 1] - 1
		if not rposx[i]:
			rposx[i] = rposx[i - 1]
		if not rposy[i]:
			rposy[i] = rposy[i - 1]
		rl[i] = min(rl[i - 1], rposx[i])
		rr[i] = max(rr[i - 1], rposx[i])
		rb[i] = min(rb[i - 1], rposy[i])
		rt[i] = max(rt[i - 1], rposy[i])
	dx = False
	dy = False
	ls = len(s) - 2
	for i in range(1, len(s) - 1):
		if (l[i] - rl[ls - i]) * (r[i] - rr[ls - i]) > 0:
			dx = True
		if (tp[i] - rt[ls - i]) * (b[i] - rb[ls - i]) > 0:
			dy = True
	wd = r[ls] - l[ls] + 1
	ht = tp[ls] - b[ls] + 1
	ans = wd * ht
	if dx:
		ans = min(ans, (wd - 1) * ht)
	if dy:
		ans = min(ans, (ht - 1) * wd)
	print(ans)
	t -= 1


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)


def lim(s):
	now = 0
	(up, down) = (0, 0)
	for i in s:
		now += i
		up = max(up, now)
		down = min(down, now)
	return (up, down)

def f(a):
	return a[0] - a[1] + 1

def upg(s):
	t = lim(s)
	(up, down) = (t[0], t[1])
	arr = [1, 1]
	now = 0
	for i in range(len(s) - 1):
		if now == up - 1 and s[i + 1] == 1 and (arr[0] == 1):
			arr[0] = 0
			if f(lim(s[:i + 1] + [-1] + s[i + 1:])) < f(t):
				return 1
		if now == down + 1 and s[i + 1] == -1 and (arr[1] == 1):
			arr[1] = 0
			if f(lim(s[:i + 1] + [1] + s[i + 1:])) < f(t):
				return 1
		now += s[i + 1]
	return 0
for q in range(int(input())):
	s = input()
	(s1, s2) = ([0], [0])
	for i in s:
		if i == 'W':
			s1.append(1)
		if i == 'S':
			s1.append(-1)
		if i == 'A':
			s2.append(1)
		if i == 'D':
			s2.append(-1)
	u1 = upg(s1)
	u2 = upg(s2)
	(res1, res2) = (f(lim(s1)), f(lim(s2)))
	ans = min((res1 - u1) * res2, (res2 - u2) * res1)
	print(ans)