问题 26033 --丢手绢

26033: 丢手绢

时间限制: 1 Sec  内存限制: 128 MB
提交: 80  解决: 27
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][800kb]

题目描述

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

输入

先输入一个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恤。 

输出

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

样例输入

3
3
RRG
5
RRRRR
4
BRBG

样例输出

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

提示

来源

[提交][状态]