# Bitcoin Toss

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 *T*ails and *H*eads), 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.

Sample Input 1 | Sample Output 1 |
---|---|

2 HTTTT THTHHTTTHHT |
1 0 2 1 |