The war goes on.The Knights and the Demons are fighting at their fullest but as expected, the evil is dominating the good ones.In order to defeat the Demons the knights have to come together.
Initially everyone is standing in a circular path at the top of the Demon tower.The warrior at index 1 is standing next to warrior at index n and before the warrior at index 2.In order to win the fight the knights have to come together.
The knights have a special power through which they can swap them self with anyone.
Help the Knights decide the minimum number of swaps they have to do so that all of them stand together.
Input
The first line of the input contains t (the number of test cases).
The next 2*t line contains the following:
The first line contains n (the size of string).
The next line contains the string s.
The ith character denotes if there is a Knight (K) or a Demon (D).
Output
The output contains an integer denoting the minimum number of swaps required for each test case t.
Constraints
1<=t<=100
1<=n<=105
In the sample test case , In first :- we can swap the K at index 3 with D at index 6 to get all D and K together.
In second : we can swap D at index 3 with K at index 2 to get all D and K together.