"""
A tu mamy mamuta! - rozwiązanie wzorcowe, algorytm Manachera (liniowy)

Znajdujemy najdłuższy palindrom w tekście i podajemy jego długość
Ignorujemy znaki przestankowe i spacje.
"""

def palindrome(text):
    """
    :param text: analizowany napis (z * pomiędzy znakami)
    :return: długość najdłuższego palindromu w napisie text
    """
    m = len(text)
    palsizes = []
    c = 0
    s = 0
    while c < m:
        # szukamy palindromu o środku w c
        while c-s-1 >= 0 and c+s+1 < m and text[c-s-1] == text[c+s+1]:
            s += 1
        palsizes.append(s) # zapamiętuje długość najdłuższego palindromu o środku w c
        # poniżej przeliczamy c i s do kolejnej iteracji korzystając ze wcześniejszych informacji
        prevc = c
        prevs = s
        c += 1
        s = 0      # domyślne wartości, ale może coś poprawimy
        while c <= prevc + prevs:
            # skorzystamy z faktu, że center leży w poprzednim palindromie a każdy znak w palindromie
            # ma odbicie lustrzane we wcześniejszej części. Użyjemy danych z tego odbicia.
            mirroredc = prevc - (c - prevc)
            maxsize = prevc + prevs - c
            if palsizes[mirroredc] < maxsize:
                palsizes.append(palsizes[mirroredc])
                c += 1
            elif palsizes[mirroredc] > maxsize:
                palsizes.append(maxsize)
                c += 1
            else:   # palsize[mirroredc] == maxsize
                s = maxsize
                break   # ten może da się powiększyć
    return max(palsizes)

n = int(input())
for i in range(n):
    # napis z usuniętymi znakami specjalnymi, konwersją na małe litery i gwiazdką pomiędzy każdymi
    # dwoma znakami (+ początek i koniec), dzięki temu szukamy tylko nieparzystych palindromów
    # do tego nawiasy jako wartownicy 
    line = "".join(["*", "*".join(input().translate(str.maketrans(
			 "", "",  " !,.?")).lower()), "*"])
    print(palindrome(line))
