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