月底了，文文没有钱了，涛涛要跟文文玩一个游戏。文文将得到一个由 "A" 和 "B" 组成的字符串s。
涛涛告诉文文可以执行以下两种操作：

1. 选择一个子串 AB，将其更改为 BC，然后得到一块钱。
2. 选择一个子串 BA，将其更改为 CB，然后得到一块钱。

问文文最多能得到多少钱？

输入
该输入由多个测试用例组成。
第一行包含一个整数t（1 ≤ t ≤ 1000）表示测试用例的数量。
每个测试用例包含字符串s（1 ≤ |s| ≤ 2e5）。
题目保证字符串s仅由”A” 和 ”B”组成， 所有测试用例中的 s 的长度之和不超过 2e5。

输出
对于每个测试用例，输出一个整数表示文文最多拿到多少钱

Input
4
ABBA
ABA
BAABA
ABB

Output
2
1
3
1

解析：
AB变BC，BA变CB
容易知道 n 个 A 和 1 个 B，可以获得 n 块金币；1 个 B 和 n 个 A，也可以获得 n 块金币。
就看 A 和左边还是右边的 B 结合了。
我们要预处理所有 AAAAB,AAB,BAA,BAAAA的情况，记录这些情况的左右端点。
之后 对于 区间[l,r]，可以更新的dp[r]=max(dp[r],dp[l-1]+r-l)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
vector <int> a[N];
vector <PII> res;
int dp[N];                          //dp[i] 表示前 i 个字符能得到的最多金币数
string str;
void solve()
{cin>>str;int n=str.size();str=" "+str;for (int i=0;i<=n;i++) a[i].clear();memset(dp,0,sizeof dp);res.clear();int cnt=0;for (int i=1;i<=n;i++)                          //记录AAAB、AAB和AB等情况{if (str[i]=='A') cnt++;else {if (cnt>0) res.push_back({i-cnt,i});cnt=0;}}if (cnt>0) res.push_back({n-cnt,n});cnt=0;for (int i=n;i>=1;i--)                          //记录BAAA、BAA和BA等情况{if (str[i]=='A') cnt++;else {if (cnt>0) res.push_back({i,i+cnt});cnt=0;}}if (cnt>0) res.push_back({1,1+cnt});cnt=0;for (auto [l,r]:res) a[l].push_back(r);for (int i=1;i<=n;i++){dp[i]=max(dp[i],dp[i-1]);int l=i;for (auto r:a[l]) dp[r]=max(dp[r],dp[l-1]+r-l);}cout<<dp[n]<<endl;
}
signed main()
{ios;int T=1;cin>>T;while (T--) solve(); return 0;
}