题目描述

Mutsumi 和她的好朋友 Mortis 正在玩一个跑酷游戏，这个跑酷游戏的规则比较特殊：

游戏中有 \(n+2\) 个格子，格子的编号从 \(0\) 到 \(n+1\)，每个格子的颜色是红、黑、白中的一个，其中第 \(i\) 个格子的颜色为 \(s_i\)，在第 \(i\) 个格子进行跳跃可以跳到第 \(j(i \le j \le n+1)\) 个格子上。

现在，Mutsumi 和 Mortis 操纵着同一个游戏角色，Mutsumi 操纵时游戏角色只能跳到红色、白色的格子上，Mortis 操纵时游戏角色只能跳到黑色、白色的格子上，每进行一次跳跃都需要切换玩家（即游戏角色的操纵者，且切换玩家时游戏角色的位置不会修改），初始时操纵游戏角色的玩家是 Mutsumi。

每一轮游戏初始时 Mutsumi 在第 0 个格子，跳到第 \(n+1\) 个格子后一轮就会结束，第 \(0\) 个格子和第 \(n+1\) 个格子的颜色都为白色。每一个红色或黑色的格子在所有轮次中只能经过一次，也就是说不能有两轮或更多轮经过同一个红色或黑色的格子。

Mutsumi 和 Mortis 想知道，至少需要几轮游戏才能经过所有的格子至少一次？

输入格式

第一行输入一个正整数 \(T(1 \le T \le 2 \times 10^5)\)，表示数据组数。

对于每一组数据：

第一行输入一个仅包含 \('R', 'B', 'W'\) 三种字符的字符串 \(s\)， \(s_i = 'R', s_i = 'B', s_i = 'W'\) 分别表示第 \(i\) 个格子颜色为红色、黑色、白色。

数据保证 \(\sum n \le 2 \times 10^6\)。

输出格式

对于每组数据，在一行中输出一个整数表示答案。

样例输入

1
RRBWRB

样例输出

2

提示

第1轮：

Mutsumi 先从第 0 个格子跳到第 1 个格子（红色）；

Mortis 从第 1 个格子跳到第 3 个格子（黑色）；

Mutsumi 从第 3 个格子跳到第 5 个格子（红色）；

Mortis 从第 5 个格子跳到第 6 个格子（黑色）；

Mutsumi 从第 6 个格子跳到第 7 个格子（白色）；

第2轮：

Mutsumi 先从第 0 个格子跳到第 2 个格子（红色）；

Mortis 从第 2 个格子跳到第 4 个格子（白色）；

Mutsumi 最后从第 4 个格子跳到第 7 个格子（白色）；

因此2轮游戏经过了所有格子至少一次，可以证明不存在更小的答案。