beecrowd | 1058

Independent Attacking Zones

By Sohel Hafiz Bangladesh*

Timelimit: 1

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 there are no two triangular regions overlap. Unfortunately, the process is more complicated 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 don’t dominate in any assignment..

Suppose we have 6 platoons (4 black and 2 red) as shown in the following figure:


Since there are 6 platoons, we can form 2 groups ( 6 / 3 = 2 ). There are two possible arrangements for this configuration.


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

Input

The first line of input is an integer T (T<100) that indicates the number of test cases. Each case consists of two lines. The first line is an integer P (2 < P < 40 and P is a multiple of 3). P represents the number of platoons. Next line consists of a string of size P. Each character of the string is either ‘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’.

Output

For each case, show the case number followed by the number of valid configurations.

Input Sample Output Sample

3
6
RBBBRB
6
BRBRBB
9
BBBBBBBBB

Case 1: 2
Case 2: 2
Case 3: 12