#include <fstream>
#include <string>

using namespace std;

#define MAX_CHARS 1000001

ifstream fin("prefix.in");
ofstream fout("prefix.out");

string str;
int numTests, map[MAX_CHARS];

void buildSufPref() {
    int len = (int)str.size();

    for (int i = 1, j = 0; i < len; ++i) {
        while (str[i] != str[j] && j) {
            j = map[j - 1];
        }

        if (str[i] == str[j]) {
            ++j;
        }

        map[i] = j;
    }
}


int main() {
    fin >> numTests;
    int len, left, right, currLen, maxLen = 0, res;
    bool first;

    while (numTests--) {
        fin >> str;

        len = str.length();
        buildSufPref();

        first = false;
        left = right =  maxLen = 0;

        for (int i = 1; i < len; ++i) {
            if (map[i] == map[i - 1] + 1) {
                if (!first) {
                    left = i;
                    first = true;
                }

                right = i;
            } else if (map[i] && map[i] == map[i - 1]) {
                left = i - 1;
            } else {
                if (first) {
                    currLen = right - left + 1;
                    right -= (currLen % left);
                    currLen -= (currLen % left);

                    if (maxLen <= currLen) {
                        maxLen = currLen;
                        res = right + 1;
                    }
                }

                first = false;
            }
        }

        if (left == 0 && right == 0) {
            fout << "0\n";
            continue;
        }

        currLen = right - left + 1;
        right -= (currLen % left);
        currLen -= (currLen % left);

        if (maxLen <= currLen) {
            maxLen = currLen;
            res = right + 1;
        }

        fout << res << '\n';
    }

    return 0;
}