Migrated from Lutece 294 Necklace

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You are given a necklace consists of $N$ beads linked as a circle. Each bead is either crystal or jade. Now, your task is:

1. Choose an arbitrary position to cut it into a chain.
2. Choose either direction to collect it.
3. Collect all the beads in the chosen direction under the constraint that the number of crystal beads in your hand is not less than the jade at any time.

Calculate the number of ways to cut meeting the constraint.

Input

In the first line there is an integer $T$, indicates the number of test cases. ($T\leq 50$) Then $T$ lines follow, each line describes a necklace. C stands for a crystal bead and J stands for a jade bead. The length of necklace is between $2$ and $10^6$.

Output

For each case, print Case x: d on a single line in which $x$ is the number of case counted from one and d is the number of ways.

Samples

2
CJCJCJ
CCJJCCJJCCJJCCJJ

Case 1: 6
Case 2: 8

Resources

2010 ACM-ICPC Multi-University Training Contest 13 Host by UESTC