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 briliant 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.
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).
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 |