A common technique used by invading armies is to surround a city instead of directly entering it. The armies divided themselves into pla- toons 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 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 dont dominate in any assignment. Suppose we have 6 platoons (4 black and 2 red) as shown in the figure on the right. Since there are 6 platoons, we can form 2 groups ( 6 / 3 = 2 ). There are two possible arrangements for this configuration. Assignment 1 Assignment 2 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 < 40andP is a multiple of3). 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, output the case number followed by the number of valid configurations.
2/2 Sample Input 3 6 RBBBRB 6 BRBRBB 9 BBBBBBBBB Sample Output Case 1: 2 Case 2: 2 Case 3: 12