Cho một chuỗi \(s\) chỉ gồm toàn các kí tự A và B. Ban đầu, Quỳnh có \(0\) điểm. Quỳnh được phép thực hiện hai thao tác sau với số lần tùy ý:

• Chọn ra hai kí tự liên tiếp bất kỳ, nếu nó là AB thì đổi thành BC và nhận \(1\) điểm
• Chọn ra hai kí tự liên tiếp bất kỳ, nếu nó là BA thì đổi thành CB và nhận \(1\) điểm

Yêu cầu: Tính số điểm tối đa mà Quỳnh đạt được

Input

• Dòng đầu tiên chứa \(t (2 \le t \le 10^4)\) là số lượng test
• \(t\) dòng tiếp theo, mỗi dòng ghi một xâu \(s\)

Tổng độ dài các xâu \(s\) trong toàn bộ \(t\) testcase nhỏ (của một testcase lớn) không vượt quá \(2 \times 10^5\))

Output

• Gồm \(t\) dòng, mỗi dòng chứa kết quả cho một testcase

Example

8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

2
1
3
1
6
2
0
0