Ross has a monkey named Marcel. He has decided to take Marcel to The Monkey Contest.
In this contest, there are n cells. On each cell, either L or R is written.
L indicates monkey should move 1 cell to the left, while R indicates monkey should move 1 cell to the right.
Each monkey is placed in a cell and then the monkey needs to follow the orders as written on the current cell. Ross found that if the monkey is placed in certain cells, it will keep moving for the lifetime. Such cells are also known as the dead cells. He doesn't want Marcel to be stuck in those cells and so he has asked your help.
Help Ross by telling the number of dead cells out of the given grid of cells.
Note:- Dead cells are those cells in which if the monkey is placed, then the monkey is stuck in an infinite loop.
See the sample case for better understanding.
Input format:
First line contains an integer T, denoting the number of test-cases.
Each testcase consists of 2 lines as shown below:-
First line contains an integer n.
Second line contains a string of size n formed of only 'L' or/and 'R', which denotes the grid of cells.
Output format:
For each testcase, print the number of dead cells.
Constraints:
1 <= t <= 8
1 <= n <= 1000000
In first testcase, if the monkey is placed in cell 1, it will move to Right (r) i.e. to cell 2 and cell 2 has Left (L) so it will move back to cell 1 and again on cell 2 and so on. Hence this becomes an infinite loop.
Thus, if the monkey is placed in either cell 1 or cell 2 then the monkey will get stuck in an infinite loop between cell 1 and cell 2. If the monkey is placed in cell 3, then it can easily move out of the grid in one move.
So, the number of dead cells are 2 (cell 1 & cell 2).
In second testcase, we can see that if we place monkey in any of the cell, the monkey can easily get out of the grid. Hence, there are no dead cells and so answer is 0.
