Ben, le cousin de Farmer John, est un scientifique fou. Cela provoque généralement des tensions aux réunions familiales, mais peut parfois aider, surtout lorsque Farmer John rencontre des problèmes inhabituels avec ses vaches.

Farmer John fait justement face à un tel problème. Il a commandé $N$ vaches ($1 \leq N \leq 1000$) de deux races : Holstein et Guernsey. Il a spécifié sa commande par une chaîne de $N$ caractères, chacun étant $H$ (Holstein) ou $G$ (Guernsey). Mais à leur arrivée, une fois alignées, leurs races formaient une autre chaîne.

Appelons les chaînes $A$ et $B$, où $A$ est la suite de races souhaitée à l’origine et $B$ celle observée à l’arrivée. Plutôt que de vérifier simplement si réarranger les vaches de $B$ suffit pour obtenir $A$, Farmer John demande l’aide du génie scientifique de Ben.

Après plusieurs mois, Ben crée une machine remarquable, multi-cow-breed-flipinator 3000, capable de changer les races de n’importe quelle sous-chaîne de vaches : tous les $H$ deviennent $G$ et tous les $G$ deviennent $H$. Farmer John veut connaître le nombre minimal d’utilisations pour transformer l’ordre actuel $B$ en l’ordre souhaité $A$. Malheureusement, les talents de Ben se limitent à inventer des appareils ingénieux : aidez Farmer John à résoudre ce problème de calcul.

Entrée

La première ligne contient $N$, et les deux suivantes les chaînes $A$ et $B$. Chacune a $N$ caractères $H$ ou $G$.

Sortie

Affichez le nombre minimal d’utilisations de la machine pour transformer $B$ en $A$.

Exemples

Entrée 1

7
GHHHGHH
HHGGGHH

Sortie 1

2

Remarque

D’abord, FJ peut transformer la sous-chaîne du seul premier caractère, changeant $B$ en GHGGGHH. Puis il transforme celle des troisième et quatrième caractères pour obtenir $A$. D’autres combinaisons de deux utilisations fonctionnent également.

Auteur du problème : Brian Dean