디왈리 조명 (라지)

디왈리는 빛의 축제다. 이날을 기념하려고 사람들은 여러 색 전구로 집을 꾸미고 폭죽을 터뜨린다. 파리도 디왈리를 무척 좋아한다. 파리는 빛을 좋아하고 초한의 힘이 있어서 빨간 전구와 파란 전구를 무한히 많이 샀다. 프로그래머답게 패턴도 좋아해서, 길이가 유한한 패턴 S를 무한히 반복해 전구를 늘어놓는다.

예를 들어 S가 BBRB이면 파리가 만드는 무한 수열은 BBRBBBRBBBRB...가 된다.

파리가 가장 좋아하는 색은 파란색이다. 그래서 자신이 만든 무한 수열에서 I번째 전구부터 J번째 전구까지에 파란 전구가 몇 개 있는지 알고 싶어 한다. 전구 번호는 1부터 시작하는 연속한 정수로 매긴다. 위 수열에 번호를 매기면 다음과 같다.

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

이 수열에서 4번째부터 8번째까지에는 파란 전구가 4개 있고, 10번째부터 12번째까지에는 2개만 있다.

수열이 아주 길어질 수 있어서 파리는 개수를 대신 세어 주는 프로그램을 짰다. 같은 일을 하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 처음 패턴을 나타내는 문자열 S가 주어진다.

각 테스트 케이스의 둘째 줄에는 위에서 정의한 두 정수 I와 J가 공백 하나로 구분되어 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 파리의 무한 수열에서 I번째 전구부터 J번째 전구까지에 들어 있는 파란 전구의 개수다.

• $1 \le T \le 100$
• $1 \le |S| \le 100$
• S의 각 문자는 대문자 B 또는 대문자 R이다.
• $1 \le I \le J \le 10^{18}$

패턴이 BR이면 홀수 번째 전구는 모두 파란색이고 짝수 번째 전구는 모두 빨간색이다. 그래서 1번부터 $10^6$번까지에는 파란 전구가 정확히 500000개 있다.