Problem E
Bitcoin Toss

Photo by Antana cc by-sa 2.0

But, Yraglac has an idea; no, it does not include tossing virtual coins, the problem title is misleading in that sense. Instead, he will print out all the possible outcomes of tosses of $N$ coins (as a string of Tails and Heads), put them into a hat and get someone to draw one out. When we become a hatless society, Yraglac will come up with another one of his brilliant plans.

Rather than putting some thought into the process, Yraglac prints a string of ‘T’s and ‘H’s of a random length and then finds the longest substring containing all possible combinations of coin tosses for some $N$ (if there are several substrings like this, he picks the largest $N$ possible).

For instance, given the string THTHHTTTHHT, he can start cutting it after the first character, $2$ characters at the time. That way he will have all possible outcomes of tossing two coins on paper: T|HT|HH|TT|TH|HT

Can you help Yraglac figure out where he should start cutting his string, such that the substring of length $N \cdot 2^ N$ contains all possible outcomes of tossing $N$ coins (when cut into pieces of length $N$)?

If there are several possibilities, you should choose as large $N$ as possible.

Input

The first line contains a single integer $T \leq 10$ giving the number of test cases. Each test case consists of a single line with a string $S$ ($2\leq |S| \leq 20\, 000$), containing only characters ‘T’ and ‘H’ (at least one of each).

Output

For the each test case, output two integers on a line: $N$ and $P$, where $N$ is as described in the problem statement and as large as possible and $P$ is the number of characters Yraglac should skip before making the first cut. If there are several possible $P$’s for the given $N$, print out the smallest one.

2
HTTTT
THTHHTTTHHT

1 0
2 1