Молекули РНК
Молекула РНК складається з послідовності чотирьох нуклеотидів: A, C, G та U. Завдяки хімічній структурі, водневі зв'язки можуть утворюватися між парами нуклеотидів (A, U), (U, A), (G, C) або (C, G), але не між іншими парами (наприклад, A не може утворити зв'язок з C або G). Кожен нуклеотид може утворити водневий зв'язок лише з одним іншим нуклеотидом, і зв'язки не можуть утворюватися між сусідніми нуклеотидами в послідовності РНК, оскільки між ними вже існує ковалентний зв'язок.
У живих клітинах РНК згинається, утворюючи багато водневих зв'язків. Проте ці зв'язки не можуть перетинатися: якщо є зв'язок від нуклеотида i до нуклеотида j (i < j), то нуклеотиди i+1, … , j−1 можуть утворювати зв'язки лише між собою і не можуть мати зв'язків з 1, …, i−1 або j+1, …, n, де n — це кількість нуклеотидів у РНК.
Реальна структура РНК є складнішою, але ми спростимо завдання для цього змагання.
Ваше завдання — визначити максимальну кількість можливих зв'язків для заданої молекули РНК.
Вхідні дані
Вхідні дані містять кілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить невід'ємне число 0 ≤ n ≤ 500. Другий рядок кожного тестового випадку містить рядок (молекула РНК) довжиною n, що складається з символів A, C, G та U. Вхідні дані завершуються "0", який не слід обробляти.
Вихідні дані
Для кожного тестового випадку виведіть максимальну кількість водневих зв'язків для заданої молекули РНК.