ACGU

$A$, $C$, $G$, $U$로 이루어진 문자열 $S$가 주어진다. 아래 규칙을 지키면서 문자들끼리 짝을 지을 수 있으며, 지을 수 있는 짝의 최대 개수를 구하려고 한다.

짝은 다음 조건을 모두 만족해야 한다.

1. $A$는 $U$와 짝을 지을 수 있다.
2. $C$는 $G$와 짝을 지을 수 있다.
3. 각 문자는 최대 한 개의 문자와만 짝을 지을 수 있다.
4. $w < x$, $y < z$, $w < y$이고 $w$번째 문자가 $x$번째 문자와, $y$번째 문자가 $z$번째 문자와 짝을 지었다고 하자. 이때 $y > x$ 또는 $z < x$ 중 적어도 하나가 참이어야 한다. 즉, 어떤 두 짝도 서로 교차해서는 안 된다.
5. $C$-$G$ 짝은 최대 $K$개까지만 지을 수 있다.

문자열 $S$는 RLE(런 길이 부호화) 형태로 주어진다. RLE는 같은 문자가 연속으로 나오는 구간을 그 문자와 반복 횟수로 나타낸다. 예를 들어 AAAACCGAAUUG는 A4C2G1A2U2G1로 부호화된다. 즉 입력은 $c_1 f_1 c_2 f_2 \ldots c_n f_n$ 형태이며, 각 $c_i$는 $A, C, G, U$ 중 하나이고 각 $f_i$는 양의 정수이다.

부호화된 문자열은 다음 네 조건을 모두 만족한다.

• $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$

지을 수 있는 짝의 최대 개수를 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$ ($T \le 200$)가 주어진다. 각 테스트 케이스는 두 줄로 주어진다. 첫째 줄에는 RLE 형태의 문자열 $S$가, 둘째 줄에는 정수 $K$ ($0 \le K \le 20$)가 주어진다.

각 테스트 케이스에 대해 Case i: p 형식으로 한 줄씩 출력한다. 여기서 $i$는 테스트 케이스 번호(1부터 시작)이고 $p$는 지을 수 있는 짝의 최대 개수이다.

첫 번째 예제의 경우, 6개의 짝을 만들 수 있다.