Xâu lệnh WASD

Bạn có một xâu $s$ gồm các lệnh điều khiển cho một con robot đồ chơi đặt trên một lưới ô vuông. Robot hiểu bốn lệnh:

• W: đi lên một ô;
• S: đi xuống một ô;
• A: sang trái một ô;
• D: sang phải một ô.

Gọi $\text{Grid}(s)$ là lưới hình chữ nhật có diện tích nhỏ nhất sao cho có thể đặt robot vào một ô nào đó của lưới rồi cho nó thực hiện toàn bộ dãy lệnh $s$ mà không bao giờ đi ra khỏi lưới. Diện tích của lưới là (số hàng) $\times$ (số cột).

Bạn có thêm bốn chữ cái dự phòng: một chữ W, một chữ A, một chữ S và một chữ D. Bạn được phép chèn nhiều nhất một trong bốn chữ cái đó vào một vị trí bất kỳ của xâu $s$ (hoặc không chèn gì).

Hãy tìm diện tích nhỏ nhất của $\text{Grid}(s)$ có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa số nguyên $T$: số truy vấn.
• $T$ dòng tiếp theo, mỗi dòng chứa một xâu $s$ gồm các ký tự thuộc $\{W,A,S,D\}$.

Dữ liệu ra

In ra $T$ dòng, mỗi dòng là diện tích nhỏ nhất của $\text{Grid}(s)$ đạt được cho truy vấn tương ứng.

Ràng buộc

• $1\le T\le 1000$
• $1\le |s|\le 2·{10}^5$
• Tổng độ dài của tất cả các xâu $s$ không vượt quá $2·{10}^5$.

Ví dụ