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.*;
import java.math.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.util.Comparator.*;

public class Main {
    FastScanner in;
    PrintWriter out;
    boolean multitests = true;
    long mod = (long) 1e9 + 7; // 998_244_353L || (long) 1e9 + 9
    ArrayList<Integer>[] graph;
    ArrayList<GraphPair>[] weightedGraph;

    private void solve() throws IOException {
        // solveA();
        // solveB();
        solveC();
        // solveD();
        // solveE();
        // solveF();
    }

    private void solveA() throws IOException {
        char[] x = in.next().toCharArray();
        char[] y = in.next().toCharArray();
        int y1 = 1;
        while (y[y.length - y1] == '0')
            y1++;
        int x1 = y1;
        while (x[x.length - x1] == '0')
            x1++;
        out.println(x1 - y1);
    }

    private void solveB() throws IOException {
        int[][][] add = new int[10][10][10];
        int[] q = new int[11];
        int ql, qr;

        for (int x = 0; x < 10; x++) {
            for (int y = 0; y < 10; y++) {
                fill(add[x][y], -1);
                ql = qr = 0;
                add[x][y][x] = 0;
                q[qr++] = x;
                add[x][y][y] = 0;
                q[qr++] = y;
                while (ql < qr) {
                    int v = q[ql++];
                    if (add[x][y][(v + x) % 10] == -1) {
                        add[x][y][(v + x) % 10] = add[x][y][v] + 1;
                        q[qr++] = (v + x) % 10;
                    }
                    if (add[x][y][(v + y) % 10] == -1) {
                        add[x][y][(v + y) % 10] = add[x][y][v] + 1;
                        q[qr++] = (v + y) % 10;
                    }
                }
            }
        }

        char[] s = in.next().toCharArray();
        int[] cnt = new int[10];
        for (int i = 1; i < s.length; i++)
            cnt[(s[i] + 10 - s[i - 1]) % 10]++;

        for (int x = 0; x < 10; x++) {
            main:
            for (int y = 0; y < 10; y++) {
                int ans = 0;
                for (int k = 0; k < 10; k++) {
                    if (cnt[k] > 0 && add[x][y][k] == -1) {
                        out.print("-1 ");
                        continue main;
                    }
                    ans += cnt[k] * add[x][y][k];
                }
                out.print(ans + " ");
            }
            out.println();
        }
    }

    private void solveC() throws IOException {
        char[] s = in.next().toCharArray();
        int n = s.length;

        long[] x = new long[n], y = new long[n];
        for (int i = 0; i < n; i++) {
            x[i] = i == 0 ? 0 : x[i - 1];
            y[i] = i == 0 ? 0 : y[i - 1];
            if (s[i] == 'W')
                y[i]++;
            else if (s[i] == 'S')
                y[i]--;
            else if (s[i] == 'A')
                x[i]--;
            else if (s[i] == 'D')
                x[i]++;
            else
                n = 1 / 0;
        }


        long[] suffMaxX = new long[n], suffMinX = new long[n];
        long[] suffMaxY = new long[n], suffMinY = new long[n];
        for (int i = n - 1; i >= 0; i--) {
            suffMaxX[i] = i == n - 1 ? x[i] : max(suffMaxX[i + 1], x[i]);
            suffMinX[i] = i == n - 1 ? x[i] : min(suffMinX[i + 1], x[i]);
            suffMaxY[i] = i == n - 1 ? y[i] : max(suffMaxY[i + 1], y[i]);
            suffMinY[i] = i == n - 1 ? y[i] : min(suffMinY[i + 1], y[i]);
        }

        long ans = Long.MAX_VALUE;
        long maxX = 0, minX = 0, maxY = 0, minY = 0;
        for (int i = 0; i < n; i++) {
            ans = min(ans, (max(maxX,
                    suffMaxX[i] - 1) - min(minX, min((i == 0 ? 0 : x[i - 1]) - 1, suffMinX[i] - 1)) + 1)
                    * (max(maxY, suffMaxY[i]) - min(minY, suffMinY[i]) + 1));
            ans = min(ans, (max(maxX,
                    max((i == 0 ? 0 : x[i - 1]) + 1, suffMaxX[i] + 1)) - min(minX, suffMinX[i] + 1) + 1)
                    * (max(maxY, suffMaxY[i]) - min(minY, suffMinY[i]) + 1));
            ans = min(ans,
                    (max(maxX, suffMaxX[i]) - min(minX, suffMinX[i]) + 1) *
                            (max(maxY, suffMaxY[i] - 1) - min(minY, min((i == 0 ? 0 : y[i - 1]) - 1, suffMinY[i] - 1)) + 1));
            ans = min(ans,
                    (max(maxX, suffMaxX[i]) - min(minX, suffMinX[i]) + 1) *
                            (max(maxY, max((i == 0 ? 0 : y[i - 1]) + 1, suffMaxY[i] + 1)) - min(minY, suffMinY[i] + 1) + 1));

            maxX = max(maxX, x[i]);
            minX = min(minX, x[i]);
            maxY = max(maxY, y[i]);
            minY = min(minY, y[i]);
        }

        out.println(ans);
    }

    private void solveD() throws IOException {

    }

    private void solveE() throws IOException {

    }

    private void solveF() throws IOException {

    }

    void shuffleInt(int[] a) {
        Random random = new Random();
        for (int i = a.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            int swap = a[j];
            a[j] = a[i];
            a[i] = swap;
        }
    }

    void shuffleLong(long[] a) {
        Random random = new Random();
        for (int i = a.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            long swap = a[j];
            a[j] = a[i];
            a[i] = swap;
        }
    }

    void reverseInt(int[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            int swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    }

    void reverseLong(long[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            long swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    }

    int maxInt(int[] a) {
        int max = a[0];
        for (int i = 1; i < a.length; i++)
            if (max < a[i])
                max = a[i];
        return max;
    }

    long maxLong(long[] a) {
        long max = a[0];
        for (int i = 1; i < a.length; i++)
            if (max < a[i])
                max = a[i];
        return max;
    }

    int minInt(int[] a) {
        int min = a[0];
        for (int i = 1; i < a.length; i++)
            if (min > a[i])
                min = a[i];
        return min;
    }

    long minLong(long[] a) {
        long min = a[0];
        for (int i = 1; i < a.length; i++)
            if (min > a[i])
                min = a[i];
        return min;
    }

    long sumInt(int[] a) {
        long s = 0;
        for (int i = 0; i < a.length; i++)
            s += a[i];
        return s;
    }

    long sumLong(long[] a) {
        long s = 0;
        for (int i = 0; i < a.length; i++)
            s += a[i];
        return s;
    }

    long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    long binpowmod(long a, long n) {
        long res = 1;
        a %= mod;
        n %= mod - 1;
        while (n > 0) {
            if (n % 2 == 1)
                res = (res * a) % mod;
            a = (a * a) % mod;
            n /= 2;
        }
        return res;
    }

    class GraphPair implements Comparable<GraphPair> {
        int v;
        long w;

        GraphPair(int v, long w) {
            this.v = v;
            this.w = w;
        }

        public int compareTo(GraphPair o) {
            return w != o.w ? Long.compare(w, o.w) : Integer.compare(v, o.v);
        }
    }

    ArrayList<Integer>[] createGraph(int n) throws IOException {
        ArrayList<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        return graph;
    }

    ArrayList<GraphPair>[] createWeightedGraph(int n) throws IOException {
        ArrayList<GraphPair>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        return graph;
    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s), 32768);
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        boolean hasNext() throws IOException {
            return br.ready() || (st != null && st.hasMoreTokens());
        }

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

        int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = in.nextInt();
            return a;
        }

        int[][] nextIntTable(int n, int m) throws IOException {
            int[][] a = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    a[i][j] = in.nextInt();
            return a;
        }

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

        long[] nextLongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = in.nextLong();
            return a;
        }

        long[][] nextLongTable(int n, int m) throws IOException {
            long[][] a = new long[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    a[i][j] = in.nextLong();
            return a;
        }

        ArrayList<Integer>[] nextGraph(int n, int m, boolean directed) throws IOException {
            ArrayList<Integer>[] graph = createGraph(n);
            for (int i = 0; i < m; i++) {
                int v = in.nextInt() - 1, u = in.nextInt() - 1;
                graph[v].add(u);
                if (!directed)
                    graph[u].add(v);
            }
            return graph;
        }

        ArrayList<GraphPair>[] nextWeightedGraph(int n, int m, boolean directed) throws IOException {
            ArrayList<GraphPair>[] graph = createWeightedGraph(n);
            for (int i = 0; i < m; i++) {
                int v = in.nextInt() - 1, u = in.nextInt() - 1;
                long w = in.nextLong();
                graph[v].add(new GraphPair(u, w));
                if (!directed)
                    graph[u].add(new GraphPair(v, w));
            }
            return graph;
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        boolean hasNextLine() throws IOException {
            return br.ready();
        }
    }

    private void run() throws IOException {
        in = new FastScanner(System.in); // new FastScanner(new FileInputStream(".in"));
        out = new PrintWriter(System.out); // new PrintWriter(new FileOutputStream(".out"));

        for (int t = multitests ? in.nextInt() : 1; t-- > 0; )
            solve();

        out.flush();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}