A. Passing the Ball
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

During a physical education class, $$$n$$$ students are lined up, numbered from $$$1$$$ to $$$n$$$ from left to right.

For each student, it is known that if they receive the ball, they will pass it either to the neighbor on their left or to the neighbor on their right. This is specified by a string $$$s$$$ of $$$n$$$ characters. Each character of the string is either L or R, where $$$s_i$$$ is L if the $$$i$$$-th student passes the ball to student $$$(i-1)$$$, or $$$s_i$$$ is R if the $$$i$$$-th student passes the ball to student $$$(i+1)$$$. The first student always passes the ball to the second, and the last one to the second last (in other words, the string $$$s$$$ starts with the character R and ends with the character L).

Consider the following process:

  • first, the first student receives the ball;
  • then, exactly $$$n$$$ times, the following occurs: the student who currently has the ball passes it to their neighbor (according to the rules described above).

Your task is to determine how many students will receive the ball at least once during this process.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10000$$$) — the number of test cases.

Each test case consists of two lines:

  • the first line contains a single integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of students;
  • the second line contains $$$s$$$ — a sequence of $$$n$$$ characters L and R. The first character of the sequence is R, and the last is L.
Output

For each test case, print one integer — the number of students who will receive the ball at least once during the described process.

Example
Input
3
4
RLRL
6
RRRRRL
9
RRLRRRRRL
Output
2
6
3
Note

In the first example, student $$$1$$$ receives the ball and passes it to student $$$2$$$, who returns it back to student $$$1$$$, who passes it back to student $$$2$$$, and so on. Only students $$$1$$$ and $$$2$$$ received the ball.

In the second example, student $$$1$$$ passes the ball to student $$$2$$$, who passes it to student $$$3$$$, who passes it to student $$$4$$$, who passes it to student $$$5$$$, who passes it to student $$$6$$$, who returns it to student $$$5$$$. Each student received the ball at least once.