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