Problem A
Illuminated Lights

There are $n$ lights in a row, all initially turned off. Some lights, when turned on, will illuminate themselves and all lights to their left. The others, when turned on, will illuminate themselves and all lights to their right. What is the minimal number of lights you need to turn on to illuminate all $n$ lights?

This image shows the result of turning on the fourth light in the first sample case. The first four lights are illuminated, and everything else is not.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) —the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) —the number of lights.

The next line of each test case contains a string $s$ consisting of $n$ characters $L$ and $R$, indicating whether the lights are pointed to the left or right.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output a single integer —the minimal number of lights that need to be turned on to illuminate everything.

5
6
LRRLRL
1
R
2
LR
10
RRRRRRRRRR
10
LLRLRLLRLR

1
1
2
1
2