#include <fstream>
#include <cstring>
using namespace std;
ifstream Gigi ("prefix.in");
ofstream Marcel ("prefix.out");
const int N=1e6 +5;
char s[N];
int main()
{
    int t;
    Gigi>>t;
    while (t--){
        Gigi>>s;
        int n=strlen(s);
        char primu=s[0];
        int i,lungime=1,prefix=0,cateprimu=0,l=1,lungimetrecut=1,cateprimuactual=0;
        int cateprimudebagat=1;
        for (i=1;i<=n;++i){
            if (s[i]==primu) break;
            ++lungimetrecut;
        }
        for (++i;i<n;++i){
            if (s[i]==primu){
                if (cateprimuactual!=cateprimu) {
                    ++cateprimuactual;
                    ++l;
                    ++lungime;
                }
                else{
                    if (lungime==lungimetrecut) {
                        prefix=i;
                        ++cateprimudebagat;
                    }
                    else{
                        lungimetrecut+=lungime;
                        cateprimu+=cateprimudebagat;
                        cateprimudebagat=1;
                    }
                    cateprimuactual=0;
                    l=1;
                    lungime=1;
                }
            }
            else{
                if (s[i]==s[l]){
                    ++l;
                    ++lungime;
                }
                else{
                    if (lungime==lungimetrecut) {
                        prefix=i;
                        ++cateprimudebagat;
                    }
                    cateprimuactual=1;
                    l=1;
                    while(i<n && s[i]!=primu){
                        ++i;
                        ++lungime;
                    }
                    lungimetrecut=i;
                    cateprimu+=cateprimudebagat;
                    cateprimudebagat=1;
                    if (s[i]!=primu) break;
                    lungime=1;
                }
            }
        }
        if (lungime==lungimetrecut) {
            prefix=i;
        }
        ///if (!prefix && s[1]==primu) prefix=2;
        Marcel<<prefix<<"\n";
    }
    return 0;
}