Problem B
Necklace

Frank the jeweller has to make an exclusive necklace for The Queen. The necklace will consist of silver and gold beads whose layout is exactly specified. All the gold beads are alike and can be used interchangeably, and so can the silver ones. Frank has prepared the beads for the job, and stuck them onto a single long pin. Now he is ready to assemble the necklace by taking the beads one by one off the pin, putting them onto the prepared string from either side, and finally joining the two ends of the string. (The join will be invisible after he is done, so it can be between any two adjacent beads on the final necklace.)

Unfortunately, the beads on the pin may not be in the same order as they will appear on the necklace. Therefore in the process of assembling the necklace, Frank will have to take beads off the pin and put them aside. However, Frank’s workshop is a great mess and he is worried he might lose some of the precious beads – and so he wants to minimize the maximum number of beads that will be lying aside at any moment in the process of assembling the necklace.

Input

The input consists of several test cases (at most $20$); each test case consists of three lines. The first line contains a single integer $L$ ($1 \leq L \leq 1000$), the number of beads in the necklace. The next line contains a string of $L$ letters, each of which is ‘G’ or ‘S’ (standing for a gold or a silver bead, respectively), that describes the final layout of the necklace. (Cut at any point and straightened out.) The third line contains a string of $L$ letters describing the order of the beads on the pin. Frank can only remove the beads from the left end of the pin. You may assume that it is possible to assemble the necklace from the beads on the pin. The test cases will be followed by a line containing a single zero.

Look at the sample input. In the first test case, Frank puts one silver bead on the string. Whichever place it will take in the final layout, both of its neighbours have to be gold, so the next three silver beads from the pin have to be stored aside. Then he can just put the remaining beads on the string, alternating gold ones from the pin and silver ones that have been set aside.

In the second case, he can put the beads from the pin straight onto the string; golden ones from one end and silver ones from other end. He does not need to set any of them aside.

Output

The output must consist of one line for each test case containing the minimum possible number of beads that Frank will have to store aside in the process of assembling the necklace.

8
GSGSGSGS
SSSSGGGG
8
SSSSGGGG
GSGSGSGS
0

3
0