1. Malá mätúca prechádzka

V jednej malej dedinke, nazývanej Štvorečkovo, žila mačka Micka s jej mačiatkom Cickou. Cicka ešte nevie, ako Štvorečkovo vyzerá, tak Micka s ňou chodí každý deň na krátku obchádzku po dedinke. Ľudia v Štvorčekove bývajú v kockatých domoch so štvorčekovým pozemkom a Micka ich rada navštevuje. Micka s Cickou rady chodia po susedoch a stretávajú známe tváre. Vždy sa ale vrátia domov, kde si po prechádzke dajú poriadnu siestu. Raz sa Micka dala viesť, aby vyskúšala, ako sa Cicka naučila chodiť po dedine. Po tejto prechádzke chce Micka povedať Cicke koľko krokov spravila zle, ale nevie koľko. Pomôž Micke nájsť, koľko krokov spravila Cicka zle.

Úloha

Máme nekonečnú štvorčekovú mapu a vieme sa pohybovať po nej zvislo a vodorovne. Dostaneme záznam cesty, ktorou Cicka šla po dedinke. Jeden znak reprezentuje posun na mape o jeden štvorček. Cicka sa chcela vrátiť do bodu, v ktorom začínala, ale niekoľkokrát sa pomýlila. Zistite, koľko najmenejkrát sa mohla Cicka na svojej predchádzke pomýliť. Môžete predpokladať, že Cicka spravila párny počet krokov.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^6\)) dĺžku cesty mačiatka. V druhom riadku vstupu je popis cesty - reťazec dĺžky \(n\) skladajúci sa so znakov L, P, H a D (doľava, doprava, hore a dole).

Pre jednotlivé sady platia takéto obmedzenia:

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo, ktoré znázorňuje najmenší počet chýb v prechadzke.

Príklady

Input:

6
DDLLHH

Output:

1

Pre tento prípad, ak by sme chceli sa vrátiť na pôvodné miesto, tak namiesto jedného kroku doľava by sme mali ísť doprava.

Input:

8
DDLLHHPP

Output:

0

Urobili sme jeden okruh a vrátili sme sa naspäť, odkiaľ sme začali.