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 that 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.

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 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 a 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, BRBBBR. You can assume that the length of the string is a multiple of 3 and not greater than 70.

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