레몬멜론쿠키

모그는 쿠키를 순서대로 $2N$개 만들어야 한다. $i$번째 쿠키를 레몬 쿠키로 만들면 $i$의 비용이 들고, 멜론 쿠키로 만들면 $2i$의 비용이 든다.

문자열 $S$의 $i$번째 문자는 $i$번째 쿠키의 종류를 나타낸다. L이면 레몬 쿠키, M이면 멜론 쿠키를 만들어야 한다. ?이면 두 종류 가운데 하나를 선택할 수 있다.

레몬 쿠키와 멜론 쿠키를 정확히 $N$개씩 만들 때 필요한 최소 비용을 구하여라. 조건을 만족할 수 없다면 -1을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

각 테스트 케이스는 다음과 같은 형식으로 주어진다.

$N$ $S$

각 테스트 케이스마다 조건을 만족하는 최소 비용을 한 줄에 출력한다. 불가능하면 -1을 출력한다.

• $1 \leq T \leq 100$.
• $1 \leq N \leq 200\,000$.
• $S$의 길이는 $2N$이다.
• $S_i$는 L, M, ? 가운데 하나이다. ($1 \leq i \leq 2N$)
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.