Solve in Python:
Kira likes to play with strings very much. Moreover he likes the shape of 'W' very much. He takes a string and try to make a 'W' shape out of it such that each angular point is a '#' character and each sides has same characters. He calls them W strings.
For example, the W string can be formed from "aaaaa#bb#cc#dddd" such as:
a
a             d
a     #     d
a   b c   d
a b   c d
#     #

He also call the strings which can generate a 'W' shape (satisfying the above conditions) W strings.
More formally, a string S is a W string if and only if it satisfies the following conditions (some terms and notations are explained in Note, please see it if you cannot understand):
- The string S contains exactly 3 '#' characters. Let the indexes of all '#' be P1 < P2 < P3 (indexes are 0-origin).
- Each substring of S[0, P1−1], S[P1+1, P2−1], S[P2+1, P3−1], S[P3+1, |S|−1] contains exactly one kind of characters, where S[a, b] denotes the non-empty substring from a+1th character to b+1th character, and |S| denotes the length of string S (See Note for details).
Now, his friend Ryuk gives him a string S and asks him to find the length of the longest W string which is a subsequence of S, with only one condition that there must not be any '#' symbols between the positions of the first and the second '#' symbol he chooses, nor between the second and the third (here the "positions" we are looking at are in S), i.e. suppose the index of the '#'s he chooses to make the W string are P1, P2, P3 (in increasing order) in the original string S, then there must be no index i such that S[i] = '#' where P1 < i < P2 or P2 < i < P3.
Help Kira and he won't write your name in the Death Note.
Note:
For a given string S, let S[k] denote the k+1th character of string S, and let the index of the character S[k] be k. Let |S| denote the length of the string S. And a substring of a string S is a string S[a, b] = S[a] S[a+1] ... S[b], where 0 ≤ a ≤ b < |S|. And a subsequence of a string S is a string S[i0] S[i1] ... S[in−1], where 0 ≤ i0 < i1 < ... <...
def frequency(s,n):
    f=[[0 for i in range(26)]for j in range(n+1)]
    count=0
    for i in range(n):
        if s[i]!="#":
            f[count][ord(s[i])-97]+=1
        else:
            count+=1
            for j in range(26):
                f[count][j]=f[count-1][j]
    return (f,count)
    
def solve(s):
    n=len(s)
    f,count=frequency(s,n)
    if count<3:
        return 0
    ans=0
    index=[]
    for i in range(n-1,-1,-1):
        if s[i]=="#":
            index.append(i)
    
    for c in range(1,count-2+1):
        if index[-2]==index[-1]+1 or index[-3]==index[-2]+1:
            index.pop()
            continue
        left=max(f[c-1])
        mid1=0
        mid2=0
        right=0
        for j in range(26):
            mid1=max(mid1,f[c][j]-f[c-1][j])
            mid2=max(mid2,f[c+1][j]-f[c][j])
            right=max(right,f[count][j]-f[c+1][j])
        if left and mid1 and mid2 and right:
            ans=max(ans,left+mid1+mid2+right)
        index.pop()
    return ans
    
for _ in range(int(input())):
    s=input()
    ans=solve(s)
    if ans:
        print(ans+3)
    else:
        print(0)