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 codeforces.educational70;

import java.io.*;
import java.util.*;

public class C {
    static InputReader in;
    static PrintWriter out;

    public static void main(String[] args) {
        //initReaderPrinter(true);
        initReaderPrinter(false);
        solve(in.nextInt());
        //solve(1);        
    }

    static void solve(int testCnt) {
        for (int testNumber = 0; testNumber < testCnt; testNumber++) {
            String s = in.next();
            int n = s.length();
            int[] psX = new int[n + 1], psY = new int[n + 1];
            long maxX = 0, minX = 0, maxY = 0, minY = 0;
            for(int i = 0; i < n; i++) {
                char c = s.charAt(i);
                if(c == 'A' || c == 'D') {
                    psY[i + 1] = psY[i];
                    psX[i + 1] = psX[i] + (c == 'A' ?  -1 : 1);
                    maxX = Math.max(maxX, psX[i + 1]);
                    minX = Math.min(minX, psX[i + 1]);
                }
                else {
                    psX[i + 1] = psX[i];
                    psY[i + 1] = psY[i] + (c == 'S' ?  -1 : 1);
                    maxY = Math.max(maxY, psY[i + 1]);
                    minY = Math.min(minY, psY[i + 1]);
                }
            }
            long best = (maxX - minX + 1) * (maxY - minY + 1);

            if(check(psX, minX, maxX)) {
                best = Math.min(best, Math.max(maxX - minX, 2) * (maxY - minY + 1));
            }
            for(int i = 0; i <= n; i++) {
                psX[i] *= -1;
            }
            if(check(psX, -maxX, -minX)) {
                best = Math.min(best, Math.max(maxX - minX, 2) * (maxY - minY + 1));
            }
            if(check(psY, minY, maxY)) {
                best = Math.min(best, Math.max(maxY - minY, 2) * (maxX - minX + 1));
            }
            for(int i = 0; i <= n; i++) {
                psY[i] *= -1;
            }
            if(check(psY, -maxY, -minY)) {
                best = Math.min(best, Math.max(maxY - minY, 2) * (maxX - minX + 1));
            }
            out.println(best);
        }
        out.close();
    }

    static boolean check(int[] ps, long lo, long hi) {
        int firstMin = -1, lastMax = -1;
        for(int i = 0; i < ps.length; i++) {
            if(firstMin < 0 && ps[i] == lo) {
                firstMin = i;
            }
            if(ps[i] == hi) {
                lastMax = i;
            }
        }
        return lastMax < firstMin;
    }

    static void initReaderPrinter(boolean test) {
        if (test) {
            try {
                in = new InputReader(new FileInputStream("src/input.in"));
                out = new PrintWriter(new FileOutputStream("src/output.out"));
            } catch (IOException e) {
                e.printStackTrace();
            }
        } else {
            in = new InputReader(System.in);
            out = new PrintWriter(System.out);
        }
    }

    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        InputReader(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream), 32768);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

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

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

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

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

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

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

        Long[] nextLongArray(int n) {
            Long[] a = new Long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }
    }
}


