Let str be a string, we define a function f(str) as follows: the number of substrings of str where all characters in each substring are the same.
For example, f(s) = 5, where s='aabc'. The substrings where all characters are the same are: s[0,0]='a', s[1,1]='a', s[0,1]='aa', s[2,2]='b', and s[3,3]='c'.
Now, given a string s, you need to find a subsequence s' of s such that f(s') is maximized. A subsequence of a string is formed by deleting some characters from the string without changing the order of the remaining characters. For example, "chy" and "cye" are subsequences of "chyen", but "cey" is not.
The first line of the input is an integer T, denoting the number of testcases. 1<= T <= 10
Next T lines indicate T strings s to find such subsequence.
1 <= length of s <= 20
Note that s only contains lowercase English alphabets.
For each testcase, let s' be the subsequence of s that maximize f(s'). Output f(s').
Remember to output '\n' at the end of each line.
In the sample testcase 1, s'='aaa'. In the sample testcase 2, s'='abbb'.