Baba has a garland of N flowers some of which are Hibiscuses, others Lotuses, and others Roses, arranged at random (i.e. the flowers are of three types - Rose, Lotus, Hibiscus). Here are two examples for n=29:
1 2 1 2
H L L H L H H L
H L L H
H H L H
H H R H
L H R R
L L H H
L L L L
L L H L
H H L H
L H H H
L H H H
H H H L
H L H H H R
Figure A Figure B
R rose
L lotus
H hibiscus
The flowers considered first and second in the text that follows have been marked in the picture.
The configuration in Figure A may be represented as a string of L’s and H’s, where L represents a lotus and H represents a hibiscus, as follows: LHLHHHLLLHHHHHLHHLLHLLLLHHHHL.
Suppose you are to break the garland at some point, lay it out straight, and then collect flowers of the same type from one end until you reach a flower of a different type, and do the same for the other end (which might not be of the same type as the flowers collected before this).
Determine the point where the garland should be broken so that the most number of flowers can be collected.
For example, for the garland in Figure A, 8 flowers can be collected, with the breaking point either between flower 9 and flower 10 or else between flower 24 and flower 25.
But, Baba has a special fondness for Roses. When collecting flowers, a Rose that is encountered may be treated as either Lotus or Hibiscus (or may be added in either lotuses or hibiscuses).
Help Baba in determining the largest number of flowers that can be collected from a supplied garland.
INPUT:
The first line contains the number of test cases, T. Each of the next T lines contains a string of N characters, each of which is R, L or H.
OUTPUT:
For each test case, output a single line containing the maximum number of flowers that can be collected.
CONSTRAINTS:
Subtask 1 (30 points):
Subtask 2 (70 points):
Original Constraints.
For Test Case 1:
Consider two copies of the garland (kind of like being able to runaround the ends). The string of 11 is marked.
Two garland copies joined here
v
RRRLLHRHLHLHHLHLHRHRRHLRHRHHL|RRRLLHRHLHLHHLHLHRHRRHLRHRHHL
******|*****
HHHHHL|LLLLL <-- assignments
5xH .....#|##### 6xL
5+6 = 11 total