ACGU

You are given a string $S$ over the alphabet $\{A, C, G, U\}$. You may form pairs between characters of $S$ under the rules below, and you want to make as many pairs as possible.

A pairing must satisfy all of the following.

1. An $A$ may be paired with a $U$.
2. A $C$ may be paired with a $G$.
3. Each character is paired with at most one other character.
4. Suppose the $w$-th character is paired with the $x$-th character and the $y$-th character is paired with the $z$-th character, where $w < x$, $y < z$, and $w < y$. Then at least one of $y > x$ or $z < x$ must hold. That is, no two pairs may cross.
5. At most $K$ of the pairs may be $C$-$G$ pairs.

The string $S$ is given in run-length encoded (RLE) form. RLE writes each run of consecutive identical characters as that character followed by the number of times it repeats; for example, AAAACCGAAUUG is encoded as A4C2G1A2U2G1. Formally the input has the form $c_1 f_1 c_2 f_2 \ldots c_n f_n$, where each $c_i \in \{A, C, G, U\}$ and each $f_i$ is a positive integer.

The encoded string satisfies all of the following.

• $f_1 + f_2 + \cdots + f_n \le 10050$
• $f_1 \le 5000$
• $f_n \le 5000$
• $f_2 + f_3 + \cdots + f_{n-1} \le 50$

Compute the maximum number of pairs that can be formed.

The first line contains the number of test cases $T$ ($T \le 200$). Each test case is given on two lines: the first line contains the string $S$ in RLE form, and the second line contains the integer $K$ ($0 \le K \le 20$).

For each test case, print a line of the form Case i: p, where $i$ is the test case number (starting from $1$) and $p$ is the maximum number of pairs that can be formed.

In the first example, six pairs can be formed.