Server Time: Wed Sep 30, 2020 9:28 pm
Welcome ( logout
H - Independent Attacking Zones
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

A common technique used by invading armies is to surround a city instead of directly entering it. The armies divided themselves into platoons having bases in a circular fashion around the city. To take internal control of the city, platoons are grouped in three to cover triangular regions. It is a policy of the General to ensure that no two triangular regions overlap. Unfortunately, the process is made a bit trickier because there are two types of armies in the invading force. The two different armies are known as Red Army and Black Army. A platoon consists of one type of army. While the Black Army has clear intention to serve the General but the Red ones might betray if they get an opportunity. It is decided that every triangular group will consist of at most one Red Army Platoon so that the Red ones cannot dominate in any assignment. Suppose we have 6 platoons (4 black and 2 red) as shown in fig 1. We have only two valid arrangements, shown in fig 2 and fig 3.

a1.png   a2.png   a3.png

You will be given the number of platoons, their positions and colors. You have to find the number of possible configurations such that every platoon is part of exactly one group and also meets the above restrictions.

Input

Input starts with an integer T (≤ 125), denoting the number of test cases.

Each case starts with a line containing a non empty string. Each character of the string is either an 'R' or 'B'. The string gives the position of the platoons in clockwise order. 'R' indicates red and 'B' indicates black. The starting position is arbitrarily chosen. So, the example above may be represented by any of the following: 'RBBBRB', 'BBBRBR', 'BBRBRB', 'BRBRBB', 'RBRBBB' or 'BRBBBR'. You can assume that the length of the string is a multiple of 3 and not great than 70.

Output

For each case, print the case number and the total number of valid configurations.

Sample Input

Output for Sample Input

3

RBBBRB

BRBRBB

BBBBBBBBB

Case 1: 2

Case 2: 2

Case 3: 12

 


Problem Setter: Sohel Hafiz
Special Thanks: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan