Photo by Antana cc
bysa 2.0
In today’s cashless society, it is becoming harder and
harder to make decisions using coin tosses, due to a lack of
physical coins.
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: THTHHTTTHHT
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
