The Gordian Dance is a traditional Bytelandian dance performed by two pairs of dancers. At the beginning the dancers are standing in the corners of the square ABCD, forming two pairs: A-B and C-D. Every pair is holding an outstretched string. So in the starting position both strings are stretched horizontally and parallel.

The dance consists of a series of moves. There are two kinds of moves:

During the dance the strings tangle with each other, but in the end they should be untangled and stretched horizontally and parallel. The dancers do not have to occupy the same spots as in the begining. The dance requires a lot of experience, because the strings can be extremely tangled during the dance. The sequence of moves after which they are no longer tangled and are stretched horizontally and parallel can be difficult to guess.

Your program should help beginner dancers end a dance. You are to determine the minimal number of mover required to end the dance given a sequence of moves already performed.

Illustration

For example after the sequence SS we get the following configuration.

The shortest sequence of moves required to end the dance is of length 5: RSRSS.

Task

Write a program which

Input

Ten test cases (given one under another, you have to process all!). The first line of each test case consists of one integer n equal to the nmber of moves already made, 0<=n<=1000000. The second line of each test case consists of one word of length n, made up of letters S and/or R.

Output

For every testcase your program should write to standard output only one line with one integer number: the minimal number of moves required to untangle the strings and stretch them horizontally and parallel.

Example

Input:
2
SS
[and 9 test cases more]

Output:
5
[and 9 test cases more]