AlgoLiga 2018

Bajtek skończył 3 lata, w związku z czym poszedł do przedszkola. Gdy dzieci w przedszkolu uczyły się literek, Bajtek potrafił już czytać. Gdy dzieci grały w warcaby, Bajtek grał z wychowawcą w szachy. Gdy dzieci uczyły się mnożyć, Bajtek ćwiczył całkowanie. I tak minęły tygodnie. Ostatnio dzieci dostały kartkę z wymieszanymi n symbolami kondensatorów oraz n symbolami cewek w szeregu i miały je połączyć w pary (tak, aby każdy kondensator miał do pary jedną cewkę). Wychowawca nie poczęstował nawet Bajtka kartą pracy uznając, że jest to dla niego zbyt proste zadanie. Niestety podczas ćwiczenia miał miejsce nieprzyjemny incydent. Jednemu z dzieci skończyła się ulubiona, zielona kredka, której używało do łączenia elementów elektronicznych. Skutkiem był płacz i zgrzytanie zębów. Problem rozwiązano pożyczając zieloną kredkę od innego malucha, lecz Bajtkowi to nie wystarczyło. Jako obrońca wszystkiego co optymalne i wydajne, Bajtek postanowił opracować algorytm, który zminimalizuje prawdopodobieństwo powtórzenia się takiej sytuacji. I udało mu się - algorytm, który pozwala na połączenie w pary kondensatorów i cewek przy zużyciu minimalnej ilości kredki. Będąc bardzo skrupulatnym chłopcem, Bajtek poprosił Cię o weryfikację jego algorytmu dla różnorakich testów.

Wejście

Wejście składa się z nieokreślonej liczby testów (mniejszej od 1001). Pierwsza linia każdego testu zawiera liczbę n (0 < n ≤ 10⁶). Druga i ostatnia linia zawiera natomiast ciąg liter {'C', 'K'} (oznaczających odpowiednio cewkę i kondensator) o długości 2n.

Wyjście

Dla każdego testu jedna liczba, będąca minimalną ilością kredki potrzebną do połączenia kondensatorów i cewki w pary.

Przykład

Wejście:
1
CK
2
CKKC
2
KKCC

Wyjście:
1
2
4

Wyjaśnienie do przykładu:

W pierwszym przykładzie mamy tylko jedną możliwość połączenia cewki i kondensatora. Zużywamy tylko 1 jednostkę kredki, gdyż odległość między cewką a kondensatorem wynosi 1.

W drugim przypadku mamy już 2 cewki i 2 możliwości połączenia. Łączymy pierwszą cewkę z pierwszym kondensatorem, albo z ostatnim. W pierwszym przypadku otrzymamy wynik 2, w drugim 4. Wybieramy oczywiście mniejszy.

W ostatnim teście są 2 optymalne rozwiązania. Niezależnie od tego z którą cewką połączymy pierwszy kondensator, i tak otrzymamy optymalny wynik. Uzyskamy albo 2+2, albo 1+3.