#include <stdio.h>
#include <string.h>
#include <unistd.h>

#define CHUNK (1 << 24)

static size_t pi[1000001];
static char buf[CHUNK];

static int read_int(size_t *bend)
{
    size_t pos = 0;
    int x = 0;

    while (buf[pos] != '\n') {
        x = x * 10 + (buf[pos] - '0');
        pos++;
    }

    *bend = pos + 1;

    return x;
}

int main(void)
{
    size_t i, q, plen, bpos, bend;
    int t;
    char *s;

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

    read(0, buf, CHUNK);
    t = read_int(&bend);

    while (t--) {
        bpos = bend;
        while (buf[bend] != '\n') {
            bend++;
        }
        bend++;

        s = buf + bpos - 1;
        plen = bend - bpos - 1;

        pi[1] = 0;
        q = 0;

        for (i = 2; i <= plen; i++) {
            while (q > 0 && s[q + 1] != s[i]) {
                q = pi[q];
            }

            if (s[q + 1] == s[i]) {
                q++;
            }

            pi[i] = q;
        }

        for (i = plen; i > 0; i--) {
            if (i % (i - pi[i]) == 0 && i - pi[i] < i) {
                break;
            }
        }

        printf("%lu\n", i);
    }

    return 0;
}