#include<bits/stdc++.h>
using namespace std;
int k;
string s,s1="",s2="";
int main()
{
	std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
	//freopen("collapse.in","r",stdin);
	//freopen("collapse.out","w",stdout);
	cin>>k;
	while(k--)
	{
		cin>>s;
		int endpos=s.size()-1;
		int ans=0;
		s1="",s2="";
		for(int i=0;i<=endpos/2;i++)
		{
			s1=s1+s[i];s2=s[endpos-i]+s2;
			//cout<<s1<<" "<<s2<<endl;
			if(s1==s2)	
			{
				if(i==endpos/2 && s.size() & 1==1)	ans++;
				else	{ans=ans+2;s1="",s2="";}
			}
			else if(s1+s2==s)	{
				cout<<1;
				goto label;
			}
			
		}
		if(s1==s2)	cout<<ans;
		else cout<<ans+1;
		label:
			cout<<endl;
	}
	return 0;
}

看起来是O(|s|*t)的复杂度，为什么会超时，|s|是字符串的长度。