描述

学姐今晚想吃寿司, doc便领着她去吃啦. 但是怎么能这样轻易就让馋嘴的学姐吃到寿司呢!
寿司店里供应了N盘寿司并排成一圈, 有些盘子是红色的, 有些盘子是蓝色的.
doc允许学姐每次交换相邻两个盘子,(第一个盘子和第N个盘子也是相邻的) 直到所有红色的盘子形成了连续的区域, 所有蓝色的盘子也形成了连续的区域.
如果学姐能通过最少的交换次数达到目标, doc就会喂学姐吃掉所有的寿司呢!

格式

输入格式

第一行一个整数T, 表示总的询问次数.
之后有T次询问, 对于每一次询问, 给出一个由R和B组成字符串.

输出格式

对于每一次询问, 输出一行.
首先输出询问的标号(参见样例输出), 之后输出最少需要的交换次数.

样例1

样例输入1

1
BBRBBRBBBRRR 

样例输出1

Case #1: 5

限制

对于40%的数据: 字符串长度 <= 1000.
对于100%的数据: 字符串长度 <= 100000, T <= 10.