Problem 26033 --丢手绢

26033: 丢手绢

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 80  Solved: 27
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][800kb]

Description

最近ACM集训队要做一个丢手绢游戏,有n个集训队员围成一圈准备开始游戏,这n个队员中有一部分人穿红色T恤,有一部分人穿绿色T恤,剩下的穿蓝色T恤,共三种颜色的T恤。悲惨的ZZY作为第一个丢手绢的人,有一个癖好,他不想看到两个穿相同颜色T恤的队员坐在一起。现在,ZZY希望聪明的你能帮他满足这个癖好,从这一圈队员中选出最少的人更换衣服(衣服只有红、绿、蓝三种颜色的),使得这一圈队员中任何相邻的两个人都穿不同颜色的衣服。两个人之间没有其它人就是相邻。

Input

先输入一个T0<T<=10000,表示下面有T组测试数据。 
每组测试包括两行。 
第一行为一个整数n(1≤n≤100),表示有n个集训队员围成一圈。 
第二行为一串字符串s,表示这n个队员的T恤颜色。这n个队员从1n编号。如果第i个字符为R表示第i号队员穿红色T恤,如果第i个字符为G表示第i号队员穿绿色T恤,如果第i个字符为B表示第i号队员穿蓝色T恤。 

Output

对于每组输入数据,先输出单独一行"Case #i:"(其中i表示第i组测试数据,从1开始),下一行再输出需要更换衣服的最少人数。

Sample Input

3
3
RRG
5
RRRRR
4
BRBG

Sample Output

Case #1:
1
Case #2:
3
Case #3:
0

HINT

Source

[Submit][Status]