디왈리 조명

Diwali는 빛의 축제이다. 이를 기념하기 위해 사람들은 여러 색의 조명으로 집을 장식하고 폭죽을 터뜨린다. 모두가 Diwali를 좋아하며, Pari도 마찬가지이다. Pari는 조명을 매우 좋아하고 초한 능력을 지니고 있어서 빨간색 전구와 파란색 전구를 무한히 많이 산다. 프로그래머인 그녀는 패턴도 좋아하므로, 주어진 유한한 패턴 S를 무한히 반복하여 조명을 배열한다.

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

파란색은 Pari가 가장 좋아하는 색이므로, 그녀는 자신이 만든 무한 수열에서 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개뿐이다.

수열이 매우 길 수 있으므로, 그녀는 자신을 대신해 개수를 세는 프로그램을 작성했다. 여러분도 똑같이 할 수 있는가?

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 30초. 메모리 제한: 1GB. 1 ≤ S ≤ 100의 길이. S의 각 문자는 대문자 B 또는 대문자 R이다.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ I ≤ J ≤ $10^{6}$.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ I ≤ J ≤ $10^{18}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄은 초기 유한 패턴을 나타내는 문자열 S로 구성된다. 각 테스트 케이스의 두 번째 줄은 위에서 정의한 공백으로 구분된 두 정수 I와 J로 구성된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 Pari의 무한 수열에서 I번째 전구부터 J번째 전구까지 양 끝을 포함한 파란색 전구의 수이다.

케이스 #1과 #2은 위에서 설명했다.

케이스 #3에서는 홀수 인덱스의 전구는 항상 파란색이고 짝수 인덱스의 전구는 항상 빨간색이므로, 위치 1부터 $10^{6}$까지 파란색 전구가 오십만 개 있다.