Touhou Red Red Blue

Problem Description

You are playing a game called Touhou Red Red Blue. In this game, you will receive $n$ mini UFOs (Undefined Fantastic Object) one by one, and you can decide to store or discard each UFO at the time you receive it. Each UFO has one of these three colors: R, G, and B. You have two bags numbered $1$ and $2$, which are initially empty. When you decided to store a UFO (marked as $U$ ) and at least one bag is empty:

• If bag $1$ is empty, store $U$ in bag $1$.
• If bag $1$ is not empty and bag $2$ is empty, store $U$ in bag $2$. When you decided to store a UFO (marked as $U$ ) and no bag is empty, we consider the three UFOs we stored(the current one, the one in the bag $1$ , and the one in the bag $2$ ) :
• If all three UFOs have the same color, these three UFOs will disappear and you get $1$ point (this is the only way you can get points). After that, you will get an additional UFO (not in the given sequence) in your bag $1$ , which color can be decided by yourself.
• If all three UFOs have different colors with each other, these three UFOs will disappear. After that, you will get two additional UFOs (not in the given sequence) in your bag $1$ and bag $2$, and you can decide their colors independently by yourself.
• Otherwise, you will discard the UFO in bag $1$, move the UFO in bag $2$ to bag $1$, and store $U$ in bag 2. What is the maximum points you can get after receiving all these $n$ UFOs?

Input

The first line contains one integer $T\ (1\le T\le 10)$ which represents the number of test cases. For each test case: One line contains one string $S\ (1\le |S|\le 10^5)$ consisting of uppercase letters 'R', 'G' and 'B', represents the color sequence of all the given UFOs.

Output

For each test case, print one line containing one integer which represents the most points you could get.

Sample Input

3
RRRRR
RBGG
RBRBR

Sample Output

2
1
1

Source

2023“钉耙编程”中国大学生算法设计超级联赛（5）