Ray and Patrick are the newest interns at AUCPL.inc. Since they are the lowest on the pecking order, they are always assigned the worst tasks, such as verifying test cases, messaging prospective sponsors on LinkedIn, and getting the managers coffee. In order to make their days more fun, they have taken to allocating their terrible tasks by flipping coins. Since they just got their first paycheck, they now have more coins to work with, so Ray devises a more advanced game for Patrick to play.

Ray first takes ~n~ coins and independently flips each of them, before arranging them in a line. Patrick is tasked with turning all the coins in the line to heads, however, due to his big hands, he can only pick up and turn over two consecutive coins at a time. For a given initial arrangement of coins, can you figure out if it is possible for Patrick to turn all the coins to heads, and if so, what is the minimum number of moves Patrick has to make, picking two consecutive coins and turning both of them over at once.

Input

The first line contains a single integer ~n~ (~2 \leq n \leq 10^5~), the number of coins tossed by Ray.

The next line contains a string of ~n~ characters. Each character is either H or T, representing the initial state of each coin in the line.

Output

Output the minimum amount of operations Patrick can take to make all the coins heads, or -1 if it is impossible. When flipping a coin, it goes from heads to tails, or tails to heads. Each operation consists of Patrick picking two consecutive coins and flipping both of them.

Example

Input 1

4
THHT

Output 1

3

Firstly, Patrick must flip the outer pairs of coins to obtain HTHT and then HTTH. Then he can flip the middle pair to obtain HHHH.

Input 2

4
HTHH

Output 2

-1

No matter what Patrick does he can't get rid of the single T.

Input 3

12
HTHTTHTHHTHT

Output 3

6

Input 4

2
HT

Output 4

-1

It is only possible here to alternate between HT and TH, never reach HH.

Input 5

2
HH

Output 5

0