Ghoplu went to the shop to buy a chain for his girlfriend. The shopkeeper has shown him a chain made of some expensive stones. The chain has n stones marked from 0 to n-1. The ith stone is connected with ((i+1)%n)th stone for each 0 ≤ i < n. Each stone can be either Ruby or Amber.

Ghoplu defines beauty factor B of a chain as the maximum number of consecutive stones of same type to impress his girlfriend.

In the chain above, the beauty factor is B = 4 because there are 4 consecutive Amber in the chain.

Ghoplu wants to chose exactly one stone i and exchange it with a stone with different type. So if the ith stone is ruby, Ghoplu will exchange it with Amber and vice-versa. He wants to do it in such a way that the value B is as small as possible.

Given the configuration of the chain, can you find the minimum value of B that Ghoplu can get after exchanging exactly one stone? Note that, It’s not allowed to change positions of the stones, the new stone must be placed in the same position as the original stone.

Note that it is mandatory to replace one stone even if the beauty factor cannot be minimized.

Input: First line contains number of test cases T (1 ≤ T ≤ 2500). For each test cases, there is a single line containing a string S (1 ≤ |S| ≤ 10^5) denoting the chain. Here |S| denotes the length or number of characters in the string. The string is made of only ’R’ (Ruby) and ’A’ (Amber). Total number of characters in the input file will be less than 5 x 10^6.

Output For each test case, print the case number and the answer in a single line. Look at the output for sample input for details.