C

Bob’s Beautiful Balls

Input: Standard Input

Output: Standard Output

 

Bob has got B balls and he would like to fill up an N x M grid with those.  Initially he is standing on cell (1,1), i.e. top left cell, and is facing east. He places the first ball there and moves one cell in the direction he is facing. If he reaches an edge of the grid or if the next move would take him to a cell containing a ball, he turns 90 degrees clockwise before making the next move. Once he lands on an empty cell, he places the next ball there. Since Bob is always concerned with beauty, he wants to see the final grid to have a beautiful configuration.

A grid has a beautiful configuration if every column has balls of the same color.

Bob does not like grids with only a single row or a single column – that means both N and M should be greater than one. Since all the cells will finally contain a ball each, the product of N and M should be equal to B. If there are multiple ways of choosing N and M, Bob will choose the pair whose sum (N+M) is minimized.

Bob has balls of three colors, Black, Grey and White and will be represented by B, G and W respectively.

As an example: Suppose Bob has 18 balls in the order BGWBBGGGBBWGBBGWBB. He can fill up a 3x6 grid as shown in the following diagram. Note that the placement orders are indicated by arrows. As you can see, all the columns have balls of the same color and thus the grid is beautiful.

 

Input

The first line of input is an integer T (T<200) that indicates the number of test cases. Each case is a line containing a string that consists of the letters {BGW} only. This ith character of the string gives the color of the ith ball. You can assume the lengths of the strings to be at least 1 and not greater than 100.

 

Output

For each case, output the case number first. If it’s possible to form a beautiful grid, output the sum (N+M) according to the description above. If it’s not possible, output "-1" instead, without quotes.

 

Sample Input                            Output for Sample Input

3

BGWBBGGGBBWGBBGWBB

GBBWBBWBBB

BBBBBBBBBBBBBBB

Case 1: 9

Case 2: -1

Case 3: 8