#include <bits/stdc++.h>
using namespace std;

string s;int n;
bool cmp_init(int a, int b)
{
	return s[a]<s[b] || (s[a]==s[b] && a<b);
}

int jmp;
vector<int> pos;
bool cmp(int a, int b)
{
	return pos[a]<pos[b] || (pos[a]==pos[b] && pos[(a+jmp)%n]<pos[(b+jmp)%n]);
}

int main() {
	int tc;cin>>tc;
	while(tc--){
	cin>>s;
	int m=s.size();
	s=s+s+"{";
	n=s.size();
	
	vector<int> SA(n,0);
	for(int i=0;i<n;i++)SA[i]=i;
	sort(SA.begin(), SA.end(), cmp_init);
	pos.assign(n,0);
	
	for(int i=1 , c=0;i<n;i++)pos[SA[i]]=(s[SA[i]]==s[SA[i-1]])?c:++c;
		
	for(jmp=1;jmp<=n;jmp*=2)
	{
		
		sort(SA.begin(), SA.end(), cmp);
		
		vector<int> tmp(n,0);
	
	    for(int i=1 , c=0;i<n;i++)tmp[SA[i]]=(pos[SA[i]]==pos[SA[i-1]] && pos[(SA[i]+jmp)%n]==pos[(SA[i-1]+jmp)%n])?c:++c;

		for(int i=0;i<n;i++)pos[i]=tmp[i];

	}
	
		for(int i=0;i<n;i++)if(SA[i]<m){cout<<SA[i]+1<<"\n";break;}
	}
	
}