Xsquare loves to eat chocolates like we all do. Xsquare's father has given him a chocolate bar B of length N where each chocolate piece is either of strawberry flavour S or of caramel flavour C. Xsquare's mom does not want him to eat all the chocolates as she thinks that consumption of too many chocolates will make him chocoholic. Therefore, she decided to take some chocolates back from him. She has some empty boxes to keep chocolates. Each box can contain exactly three chocolates. No box can contain all the chocolates of same flavour. She has ordered Xsquare to return her back, the longest contiguous sub-bar of the original chocolate bar such that she can place every three consecutive chocolates from that contiguous chocolate bar in an empty box. Each empty box can accomodate exactly three chocolates, neither less, nor more. A sub-bar is defined as contiguous peices of chocolates in some particular range.

Xsquare agrees to whatever his mom has ordered. Now, he is wondering how many chocolates he is able to eat at the end after he returns the longest contiguous sub-bar.

Help him in accomplishing this task.

Sample Example Image :

Input :

First line of input contains a single integer T denoting the number of test cases. Each of the next T line of input contains a string B denoting the chocolate bar, where i^th character in the j^th line denotes the flavour of i^th chocolate piece in j^th chocolate bar.

Output :

Output consists of T lines, each containing number of chocolates Xsquare manages to eat at the end.

Constraints :

• 1 ≤ T ≤ 10⁵
• 1 ≤ |B| ≤ 10⁶
• String B consists of character 'S' and 'C' only.
• sum of |B| over all test cases does not exceed 10⁶

Subtasks :

• sum of |B| over all test cases does not exceed 10⁶ : ( 40 pts )
• sum of |B| over all test cases does not exceed 10⁶ : ( 60 pts )

Warning :

Prefer to use scanf / printf instead of cin / cout .