#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e7+5;
const int mod=998244353;
int T;
string s;
int n,cnt;
int a[N],sum[N];
int st[N],top;
int ans;
int nxt[N],h[N],to[N];
int kmp(){
	nxt[1]=0;
	for(int i=2,j=0;i<=n;i++){
		while(j&&h[i]!=h[j+1])j=nxt[j];
		if(h[i]==h[j+1])j++;
		nxt[i]=j;
	}
	int tmp=n-nxt[n];
	return n%tmp?n:tmp;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>s;
		s=' '+s;
		n=s.size()-1;
		ans=top=0;
		for(int i=1;i<=n;i++)nxt[i]=to[i]=h[i]=0;
		for(int i=1;i<=n;i++)a[i]=(s[i]-'0'),cnt+=a[i];
		if(cnt*2>n){
			for(int i=1;i<=n;i++)a[i]^=1;
			reverse(a+1,a+1+n);
		}
		for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(a[i]?1:-1);
		rotate(a+1,max_element(sum+1,sum+n+1)-sum+a+1,a+n+1);
		for(int i=n,lst=-1,tot=0;i>=1;i--){
			if(!a[i])continue;
			if(lst!=-1){
				st[++top]=++tot;
				top-=min(top,lst-i-1);
			}
			if(top){
				ans=max(ans,tot-st[1]+1);
				to[i]=top;
			}
			lst=i;
		}
		for(int i=1;i<=n;i++){
			if(!a[i])continue;
			h[(i+ans-to[i]-1)%n+1]=1;
		}
		cout<<(ans+kmp())%mod<<"\n";
	}
	return 0;
}