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).
//package com.company;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution_C {
    static class Point {
        public long x, y;

        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Rectangle {
        public Point downLeft;
        public Point topRight;

        public Rectangle(Point a, Point b) {
            downLeft = a;
            topRight = b;
        }

        public Rectangle(Rectangle r) {
            downLeft = r.downLeft;
            topRight = r.topRight;
        }

        public long getArea() {
            return (topRight.x - downLeft.x + 1) * (topRight.y - downLeft.y + 1);
        }
    }

    public static long calcArea(Rectangle a, Rectangle b) {
        long minX = Math.min(Math.min(a.downLeft.x, a.topRight.x), Math.min(b.downLeft.x, b.topRight.x));
        long maxX = Math.max(Math.max(a.downLeft.x, a.topRight.x), Math.max(b.downLeft.x, b.topRight.x));
        long minY = Math.min(Math.min(a.downLeft.y, a.topRight.y), Math.min(b.downLeft.y, b.topRight.y));
        long maxY = Math.max(Math.max(a.downLeft.y, a.topRight.y), Math.max(b.downLeft.y, b.topRight.y));

        Rectangle r = new Rectangle(new Point(minX, minY), new Point(maxX, maxY));
        return r.getArea();
    }

    public static long solve(String s) {
        List<Point> positions = new ArrayList<>();
        List<Rectangle> rectangles = new ArrayList<>();
        long currX = 0, currY = 0;
        long minX = 0, maxX = 0;
        long minY = 0, maxY = 0;

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == 'W') {
                currY++;
            }
            else if(s.charAt(i) == 'S') {
                currY--;
            }
            else if(s.charAt(i) == 'D') {
                currX++;
            }
            else if(s.charAt(i) == 'A') {
                currX--;
            }

            positions.add(new Point(currX, currY));
            minX = Math.min(minX, currX);
            maxX = Math.max(maxX, currX);
            minY = Math.min(minY, currY);
            maxY = Math.max(maxY, currY);
            rectangles.add(new Rectangle(new Point(minX, minY), new Point(maxX, maxY)));
//            System.out.println("currArea: " + rectangles.get(rectangles.size()-1).getArea());
        }

        minX = positions.get(positions.size() -1 ).x; maxX = positions.get(positions.size() -1 ).x;
        minY = positions.get(positions.size() -1 ).y; maxY = positions.get(positions.size() -1 ).y;

        long result = rectangles.get(rectangles.size() - 1).getArea();

        for(int i = positions.size() - 1; i >= 0; i--) {
            currX = positions.get(i).x;
            currY = positions.get(i).y;

            minX = Math.min(minX, currX);
            maxX = Math.max(maxX, currX);
            minY = Math.min(minY, currY);
            maxY = Math.max(maxY, currY);

            Rectangle currR = new Rectangle(new Point(minX, minY+1), new Point(maxX, maxY+1));
            result = Math.min(result, calcArea(rectangles.get(i), currR));

            currR = new Rectangle(new Point(minX, minY-1), new Point(maxX, maxY-1));
            result = Math.min(result, calcArea(rectangles.get(i), currR));

            currR = new Rectangle(new Point(minX+1, minY), new Point(maxX+1, maxY));
            result = Math.min(result, calcArea(rectangles.get(i), currR));

            currR = new Rectangle(new Point(minX-1, minY), new Point(maxX-1, maxY));
            result = Math.min(result, calcArea(rectangles.get(i), currR));
        }

        return result;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        FastScanner sc = new FastScanner(in);
        PrintWriter out = new PrintWriter(System.out);

        int T = sc.nextInt();

        for(int i = 0; i < T; i++) {
            String s = sc.nextToken();
            out.println(solve(s));
        }

//        Rectangle r1 = new Rectangle(new Point(0 , 0), new Point(0, 1));
//        Rectangle r2 = new Rectangle(new Point(1 , 0), new Point(1, 1));
//        Rectangle r3 = new Rectangle(new Point(0 , 0), new Point(1, 1));
//        System.out.println(calcArea(r1, r2));
//        System.out.println(r3.getArea());

        out.close();
    }
}

/* Class that simulates Scanner - but Faster?(taken from user on CodeForces) */
class FastScanner {
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }

    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}
