Play with strings

Gennady likes strings very much. He likes to solve most problems involving strings. So this problem contains strings and strings only. You will be given a string S with lower-case alphabets only. You have to count the number of substrings which start and end at the same character and has an odd length. Input First line contains a positive integer T denoting the number of test cases. For each t