ABBB

Cho một xâu ký tự $s$ chỉ gồm các ký tự 'A' và 'B'. Mỗi phép thao tác, bạn được chọn một xâu con liên tiếp bằng "AB" hoặc "BB" và xoá xâu con đó khỏi $s$; phần còn lại của $s$ sẽ được ghép lại liền nhau.

Bạn có thể thực hiện thao tác trên bao nhiêu lần tuỳ ý. Nhiệm vụ là tìm độ dài nhỏ nhất của xâu sau khi thực hiện một số thao tác.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $t$ — số test ($1\le t\le 20000$).
• $t$ dòng tiếp theo, mỗi dòng chứa một xâu $s$ khác rỗng chỉ gồm các ký tự 'A' và 'B'.

Tổng độ dài của tất cả các xâu $s$ trong một file không vượt quá $2·{10}^5$.

Dữ liệu ra

Với mỗi test, in ra trên một dòng độ dài nhỏ nhất có thể đạt được của xâu $s$.

Ràng buộc

• $1\le t\le 20000$
• $1\le |s|$
• $\sum |s|\le 2·{10}^5$

Ví dụ