杂题——ABBC or BACB

ABBC or BACB

You are given a string $s$ made up of characters $\texttt{A}$ and $\texttt{B}$. Initially you have no coins. You can perform two types of operations:

  • Pick a substring$^\dagger$ $\texttt{AB}$, change it to $\texttt{BC}$, and get a coin.
  • Pick a substring$^\dagger$ $\texttt{BA}$, change it to $\texttt{CB}$, and get a coin.

What is the most number of coins you can obtain?

$^\dagger$ A substring of length $2$ is a sequence of two adjacent characters of a string.

Input

The input consists of multiple test cases. The first line of the input contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The only line of each test case contains the string $s$ ($1 \leq |s| \leq 2 \cdot 10^5$). All characters of $s$ are either $\texttt{A}$ or $\texttt{B}$.

The sum of the lengths of $s$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the maximum number of coins you can obtain.

Example

input

1
2
3
4
5
6
7
8
9
8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

output

1
2
3
4
5
6
7
8
2
1
3
1
6
2
0
0

Note

In the first test case you can perform the following operations to get $2$ coins:

$$
\color{red}{\texttt{AB}}\texttt{BA} \to \texttt{BC}\color{red}{\texttt{BA}} \to \texttt{BCCB}
$$

In the second test case you can perform the following operation to get $1$ coin:

$$
\color{red}{\texttt{AB}}\texttt{A} \to \texttt{BCA}
$$

In the third test case you can perform the following operations to get $3$ coins:

$$
\color{red}{\texttt{BA}}\texttt{ABA} \to \texttt{CBA}\color{red}{\texttt{BA}} \to \texttt{C}\color{red}{\texttt{BA}}\texttt{CB} \to \texttt{CCBCB}
$$

翻译

您将获得一个由字符 $\texttt{A}$ 和 $\texttt{B}$ 组成的字符串 $s$ 。最初你没有硬币。您可以执行两种类型的操作：

  • 选择一个子字符串 $^\dagger$ $\texttt{AB}$ ，将其更改为 $\texttt{BC}$ ，并获得一枚硬币。
  • 选择一个子字符串 $^\dagger$ $\texttt{BA}$ ，将其更改为 $\texttt{CB}$ ，然后获得一枚硬币。

您最多可以获得多少金币？

$^\dagger$ 长度为 $2$ 的子字符串是字符串的两个相邻字符的序列。

输入

输入由多个测试用例组成。输入的第一行包含一个整数 $t$ ( $1 \leq t \leq 1000$ ) - 测试用例的数量。

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

所有测试用例的 $s$ 的长度总和不超过 $2 \cdot 10^5$ 。

输出

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

Example

input

1
2
3
4
5
6
7
8
9
8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

output

1
2
3
4
5
6
7
8
2
1
3
1
6
2
0
0

笔记

在第一个测试用例中，您可以执行以下操作来获取 $2$ 币：

$$
\color{red}{\texttt{AB}}\texttt{BA} \to \texttt{BC}\color{red}{\texttt{BA}} \to \texttt{BCCB}
$$

在第二个测试用例中，您可以执行以下操作来获取 $1$ 币：

$$
\color{red}{\texttt{AB}}\texttt{A} \to \texttt{BCA}
$$

在第三个测试用例中，您可以执行以下操作来获取 $3$ 币：

$$
\color{red}{\texttt{BA}}\texttt{ABA} \to \texttt{CBA}\color{red}{\texttt{BA}} \to \texttt{C}\color{red}{\texttt{BA}}\texttt{CB} \to \texttt{CCBCB}
$$

思路

推论一、每个B都可以使它的左右任意一边的A都变成硬币，例如AAAB，可以从左开始变，变成3个硬币

推论一继续延申

1.只要有n个B，就可以使N个区间内的A变成硬币（有多少A就有多少硬币）
2. 以AAB….BA为例，需要舍去最小A区间。
3.如果两个B相连，则可以获得所有A。如…AAA BB AAA…
4.B在开头或者结尾，也都可以获得所有A。以B开头为例，所有B只要清空右边的A，即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;
int t,n,Min,c[N],z[N];

void solve() {
    memset(c, -1,sizeof c);
    memset(z, 0, sizeof z);
    Min = N;
    string s;
    cin >> s;
    n = 0;
    for (int i=0;i<s.size();i++){
        if (s[i]=='B') {
            c[++n]=i;
            z[n]=c[n]-c[n-1]-1;
            Min=z[n]<Min?z[n]:Min;
        }

        z[n+1]=s.size()-c[n]-1;
        Min=z[n+1]<Min?z[n+1]:Min;
    }
    cout << s.size() - n - Min << ed;
}


int main()
{
    
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    return 0;
}