1416: Touhou Red Red Blue
[命题人 : ]
题目描述
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?
In this game, you will receive $n$ mini UFOs (Undefined Fantastic ob
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?
输入
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.
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.
输出
For each test case, print one line containing one integer which represents the most points you could get.
样例输入 Copy
3
RRRRR
RBGG
RBRBR
样例输出 Copy
2
1
1