#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <unordered_map>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>

#define nmax 1000010
#define fst first
#define snd second
#define pb push_back
#define MOD 998244353
#define SZ(x) ((int)(x.size()))

using namespace std;

typedef pair<int, int> pii;
typedef long long int ll;

int t;
int z[nmax];
char s[nmax];

int main()
{
    freopen("prefix.in", "r", stdin);
    freopen("prefix.out", "w", stdout);

    scanf("%d", &t);

    while (t--)
    {
        scanf("%s", s + 1);

        int n = strlen(s + 1);

        memset(z, 0, sizeof(z));

        z[1] = 0;

        int l = 1, r = 1;

        for (int i = 2; i <= n; i++) {

            if (i > r) {

                l = r = i;

                while (r <= n && s[r] == s[r - l + 1]) r++;

                z[i] = r - l; r--;
            }
            else
            {
                int pos = i - l + 1;

                if (i + z[pos] <= r) z[i] = z[pos]; else
                {
                    l = i;

                    while (r <= n && s[r] == s[r - l + 1]) r++;

                    z[i] = r - l; r--;
                }
            }
        }

        int sol = 0;

        for (int i = 2; i <= n; i++)
            if (z[i] >= i - 1) sol = max(sol, ((i + z[i] - 1) / (i - 1)) * (i - 1));

        printf("%d\n", sol);
    }

    // IMPORTANT!!!!!
    // Are you missing something????
    // check limits, int or ll

    return 0;
}