Молекулы РНК
Молекула РНК представляет собой последовательность из четырех нуклеотидов: 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", которую обрабатывать не нужно.
Выходные данные
Для каждого теста выведите максимальное количество водородных связей, которые можно образовать для данной молекулы РНК.