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 < ... < in−1 < |S|.
For example, let S be the string "kira", then S[0] = 'k', S[1] = 'i', S[3] = 'a', and |S| = 4. All of S[0, 2] = "kir", S[1, 1] = "i", and S[0, 3] = "kira" are substrings of S, but "ik", "kr", and "arik" are not. All of "k", "kr", "kira", "kia" are subsequences of S, but "ik", "kk" are not.
From the above definition of W string, for example, "a#b#c#d", "aaa#yyy#aaa#yy", and "o#oo#ooo#oooo" are W string, but "a#b#c#d#e", "#a#a#a", and "aa##a#a" are not.

-----Input-----
First line of input contains an integer T, denoting the number of test cases. Then T lines follow. Each line contains a string S.

-----Output-----
Output an integer, denoting the length of the longest W string as explained before. If S has no W string as its subsequence, then output 0.

-----Constraints-----

• 1 ≤ T ≤ 100
• 1 ≤ |S| ≤ 10000 (104)
• S contains no characters other than lower English characters ('a' to 'z') and '#' (without quotes)

-----Example-----
Input:
3
aaaaa#bb#cc#dddd
acb#aab#bab#accba
abc#dda#bb#bb#aca

Output:
16
10
11

-----Explanation-----
In the first case: the whole string forms a W String.
In the second case: acb#aab#bab#accba, the longest W string is acb#aab#bab#accba
In the third case: abc#dda#bb#bb#aca, note that even though abc#dda#bb#bb#aca (boldened characters form the subsequence) is a W string of length 12, it violates Ryuk's condition that there should not be any #'s inbetween the 3 chosen # positions. One correct string of length 11 is abc#dda#bb#bb#aca

见题面

见题面