SPOJ in Gyumri

   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.

Input

   There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers 0 ≤ n ≤ 500. 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.

Output

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

Examples