eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

RNA Molecules

RNA Molecules

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

The RNA molecule is a sequence of four nucleotides A, C, G, and U. Due to the chemical structure of nucleotides, there could be hydrogen bonds established between any pair of (A, U), (U, A), (G, C) or (C, G) nucleotides, but not for the other cases (i.e. for instance A can’t make a hydrogen bond with either C or G). Every nucleotide can have hydrogen bond with at most one other nucleotide, and there could not be any hydrogen bond between two nucleotides that are adjacent in the RNA sequence as there is already a covalent interaction between them.

In the living cells, RNA will fold and there would be many hydrogen bonds established. But the hydrogen bonds can’t cross each other, i.e. if there is a bond from nucleotide i to nucleotide j (i < j), the nucleotides i+1, … , j−1 can have bonds only between themselves, and can’t have any bonds to either 1, …, i−1 or j+1, …, n where n is the number of nucleotides in the RNA.

The real case for RNA is more complicated, but we are not going to face you so much complexities in this competition, making your life easier.

Your task is to find the maximum possible bonds for a set of given RNA molecules.

Вхідні дані

There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers 0n500. The second line of each test case contains a string (RNA molecule) of size n consisting of characters A, C, G, and U. The input terminates with "0" which should not be processed.

Вихідні дані

For each test case, output the maximum number of hydrogen bonds for the given RNA molecule.

Приклад

Вхідні дані #1
2
AU
4
AGCU
4
AGUC
0

Вихідні дані #1
0
1
1
Джерело 11th Iran Internet Programming Contest, 28 November, 2013 (7 Azar, 1392)