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

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

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 \le T \le 1000~

Subtask	Score	Constraints
1	5%	~3 \le n \le 10~, the sum of ~n~ across all strings will not exceed ~10\,000~
2	20%	~3 \le n \le 2\,000~, the sum of ~n~ across all strings will not exceed ~10\,000~
3	75%	~3 \le n \le 750\,000~, the sum of ~n~ across all strings will not exceed ~750\,000~

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