Zookeeper đang chơi một trò chơi. Trong trò chơi này, Zookeeper được cho một chuỗi bao gồm các chữ cái 'A' và 'B'. Anh ta có thể thực hiện xóa một chuỗi con là "AB" hoặc "BB". Khi anh ta xóa một chuỗi con như vậy, các phần còn lại của chuỗi được ghép lại với nhau. Ví dụ, Zookeeper có thể sử dụng hai hoạt động như vậy: "AABABBA" → "AABBA" → "AAA". Zookeeper tự hỏi chuỗi ngắn nhất mà anh ta có thể tạo ra là gì. Bạn có thể giúp anh ta tìm độ dài của chuỗi ngắn nhất?

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương ~t (1 ≤ t ≤ 20000)~ – số lượng xâu cần xóa.
• t dòng tiếp theo, mỗi dòng chỉ chứa một chuỗi s gồm hai chữ cái 'A' và 'B'.

Trong đó, tổng độ dài các chuỗi trong file input không vượt quá 2x~10^5~ ký tự

Kết quả:

• Gồm t dòng, mỗi dòng đưa ra độ dài ngắn nhất của chuỗi tương ứng sau khi xóa.

Ví dụ:

INPUT

3
AAA
BABA
AABBBABBBB

OUTPU

3
2
0