You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

剪刀石头布

R 表示石头 $Rock$

S 表示剪刀 $Scissors$

P 表示布 $Paper$

题目描述

大明和新新在玩剪刀石头布, 他们将进行 $n$ 次游戏, 假如大明知道新新的出拳策略, 游戏就会变得简单, 但是大明不能连续两次出相同的招式, 在这种情况下, 大明最多能赢几局？

输入格式

第一行一个整数 $t$ 表示 $t$ 组数据

接下来 $t$ 组数据, 每组数据的第一行是一个整数 $n$ 表示一共进行了 $n$ 次游戏, 第二行是 $n$ 个符号, 表示新新的出拳策略.

输出格式

输出 $t$ 个整数表示每组游戏中大明最多能赢几局?

样例 #1

样例输入 #1

3
5
RPRRS
1
S
4
RRRR

样例输出 #1

4
1
2

提示

• $2 \le t \le 50$
• $1 \le n \le 10^5$