Bob has a collection of strings. Each string consists of the characters R
and W
. He considers a string to be Canadian if it can be split into three nonempty, contiguous segments of Rs, Ws, and Rs, in that order.
Here are some examples of Canadian flags: RWR
, RRWWRR
, RRRRWRR
.
Examples of strings that are not Canadian flags: RWW
, RRRRR
, RWRW
.
For each string in Bob's collection, find the minimum number of characters that must be changed to make the string Canadian.
Input Specification
The first line will contain
Then
Output Specification
For each string in Bob's collection, find the minimum number of characters that must be changed to make the string Canadian.
Constraints
Subtask | Score | Constraints |
---|---|---|
1 | 5% | |
2 | 20% | |
3 | 75% |
Sample Input
8
3
RWR
3
WWW
3
WRR
4
RWRW
6
WWWRRR
6
WWRRWW
10
RRRRWWRWRR
10
WWRRWWWWRW
Sample Output
0
2
2
1
1
3
1
3
Explanation
Here is a possible result for each string:
RWR
RWR
RWR
RWWR
RWWRRR
RRRRWR
RRRRWWRRRR
RRRRWWWWRR
Comments
O Canada! Our home and native land! True patriot love in all of us command. With glowing hearts we see thee rise, The True North strong and free! From far and wide, O Canada, we stand on guard for thee. God keep our land glorious and free! O Canada, we stand on guard for thee. O Canada, we stand on guard for thee.