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

Subtask | Score | 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
```

## Comments