Diwali lightings (Large)

Diwali is the festival of lights. To celebrate it, people decorate their houses with multi-color lights and burst crackers. Pari loves Diwali too. She is very fond of lights and she has transfinite powers, so she buys an infinite number of red and blue light bulbs. As a programmer she also loves patterns, so she arranges her lights by repeating a given finite pattern S forever.

For example, if S is BBRB, the infinite sequence Pari builds is BBRBBBRBBBRB...

Blue is Pari's favorite color, so she wants to know how many blue bulbs sit between the Ith bulb and the Jth bulb of that infinite sequence, inclusive. Bulbs are numbered with consecutive integers starting from 1. In the sequence above the numbering looks like this.

B  B  R  B  B  B  R  B  B  B  R  B...
1  2  3  4  5  6  7  8  9  10 11 12

There are 4 blue bulbs between positions 4 and 8, but only 2 between positions 10 and 12.

The sequence can get very long, so Pari wrote a program that does the counting for her. Write a program that does the same.

The first line of the input gives the number of test cases, T. T test cases follow.

The first line of each test case holds a string S, the initial finite pattern.

The second line of each test case holds two space separated integers I and J, defined above.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of blue bulbs between the Ith bulb and the Jth bulb of Pari's infinite sequence, inclusive.

• $1 \le T \le 100$
• $1 \le |S| \le 100$
• Each character of S is either the uppercase letter B or the uppercase letter R.
• $1 \le I \le J \le 10^{18}$

If the pattern is BR, every bulb at an odd index is blue and every bulb at an even index is red, so there are exactly 500000 blue bulbs between positions 1 and $10^6$.