#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
const int mod=998244353;
struct mint{
    int x;mint(int o=0){x=o;}mint&operator+=(mint a){return(x+=a.x)%=mod,*this;}mint&operator-=(mint a){return(x+=mod-a.x)%=mod,*this;}
    mint&operator*=(mint a){return(x=1ll*x*a.x%mod),*this;}mint&operator^=( int b){mint a=*this;x=1;while(b)(b&1)&&(*this*=a,1),a*=a,b>>=1;return*this;}
    mint&operator/=(mint a){return*this*=(a^=mod-2);}friend mint operator+(mint a,mint b){return a+=b;}friend mint operator-(mint a,mint b){return a-=b;}
    friend mint operator*(mint a,mint b){return a*=b;}friend mint operator/(mint a,mint b){return a/=b;}friend mint operator^(mint a,int b){return a^=b;}
    mint operator-(){return 0-*this;}bool operator==(const mint b)const{return x==b.x;}
};
char s[1000005];
int dp[505][505][505];
//有多少 TA, 有多少个 T.
void solve(){
	scanf("%s",s+1);
	int n=0;
	int l=strlen(s+1);
	for(int i=1;i<=l;i++){
		if(s[i]=='C'||s[i]=='A'||s[i]=='T')s[++n]=s[i];
	}
	reverse(s+1,s+n+1);
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)dp[i][j][k]=-(1ll<<60);
	}
	if(n<=50){
		dp[0][0][0]=0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=n;j++){
				for(int k=0;k<=n;k++){
					if(dp[i-1][j][k]<0)continue;
					dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
					if(s[i]=='A'){
						if(k)dp[i][j+1][k-1]=max(dp[i][j+1][k-1],dp[i-1][j][k]);
					}
					else if(s[i]=='T'){
						dp[i][j][k+1]=max(dp[i][j][k+1],dp[i-1][j][k]);
						if(j)dp[i][j-1][k]=max(dp[i][j-1][k],dp[i-1][j][k]+1);
					}
					else{
						if(j)dp[i][j-1][k]=max(dp[i][j-1][k],dp[i-1][j][k]+1);
					}
				}
			}
		}
		int res=0;
		for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)res=max(res,dp[n][i][j]);
		printf("%lld\n",res);return;
	}
}
signed main(){
	int t=read();
	while(t--)solve();
	return 0;
}