题目描述

你被给定一个由字符 A 和 B 组成的字符串 $s$。最初，你没有硬币。你可以执行两种类型的操作：

选择一个子字符串 AB，将其更改为 BC，并获得一个硬币。

选择一个子字符串 BA，将其更改为 CB，并获得一个硬币。

你能获得的最大硬币数量是多少？

输入格式

输入包含多个测试用例。输入的第一行包含一个整数 $t(1≤t≤1000)$ — 测试用例的数量。

每个测试用例的唯一一行包含字符串 $s(1≤|s|≤2×10^5)$。$s$ 的所有字符都是 A 或 B。

所有测试用例中 $s$ 的长度之和不超过 $2×10^5$。

输出格式

对于每个测试用例，输出一个整数 — 你能获得的最大硬币数量。

测试样例

8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

2
1
3
1
6
2
0
0

样例说明

在第一个测试用例中，你可以执行以下操作来获得 $2$ 个硬币： ABBA→BCBA→BCCB

在第二个测试用例中，你可以执行以下操作来获得 $1$ 个硬币： ABA→BCA

在第三个测试用例中，你可以执行以下操作来获得 $3$ 个硬币： BAABA→CBABA→CBACB→CCBCB