View as PDF

Points: 7 (partial)
Time limit: 3.0s
Memory limit: 256M

Authors:
Problem type

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 , the number of strings.

Then test cases follow. Each will contain a single integer on its own line, the length of the string, and a string .

#### 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

1 5% , the sum of across all strings will not exceed
2 20% , the sum of across all strings will not exceed
3 75% , the sum of across all strings will not exceed

#### 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