Сегодня в цирке необычное представление — на арене одновременно выступают хомячки и тигры! Все они выстроились в круг по краю арены, и теперь перед дрессировщиком стоит непростая задача: он хочет переставить животных так, чтобы все хомячки стояли подряд и все тигры тоже стояли подряд. Чтобы не создавать столпотворения, дрессировщик меняет животных парами. Он подает команду двум животным выйти из круга и поменяться местами. Поскольку хомячки в присутствии тигров ощущают себя крайне некомфортно, да и тигры нервничают в присутствии большого количества потенциальной добычи (состоящей не только из хомячков, но и из более аппетитных зрителей), дрессировщик хочет справиться с перестановкой животных как можно быстрее, т.е. за наименьшее количество обменов. Ваша задача — помочь ему.
Выходные данные
Выведите единственное число — наименьшее количество обменов, позволяющее дрессировщику достичь своей цели.
Примечание
В первом примере никого не нужно менять местами, потому что животные каждого вида и так стоят подряд. Во втором примере можно поменять, например, тигра в позиции 2 с хомячком в позиции 5 и затем — тигра в позиции 9 с хомячком в позиции 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
HTH
|
0
|
|
2
|
9
HTHTHTHHT
|
2
|