페인터

최근 그림 그리기를 공부하기 시작했고, 첫 수업 중 하나에서 세 가지 원색 Red, Yellow, Blue를 배웠다. 이 색을 조합하면 더 많은 색을 만들 수 있다. 지금까지 배운 조합은 다음과 같다.

• Red + Yellow = Orange
• Red + Blue = Purple
• Yellow + Blue = Green
• Red + Yellow + Blue = Gray

아직 색의 농도는 이해하지 못하므로, 조합에서 각 색의 비율과 순서는 중요하지 않다. 예를 들어 Red와 Yellow를 조합한 결과는 Yellow와 Red를 조합한 결과와 같고, Red, Yellow, Red를 다시 조합한 결과와도 같다.

실력을 연습하기 위해 길이 $N$인 1차원 그림 $P$를 그리고 싶다. 그림은 $N$개의 정사각형으로 이루어진다. 왼쪽에서 오른쪽으로 $P_i$는 $i$번째 정사각형의 색을 나타낸다. 처음에는 모든 정사각형이 Uncolored 상태, 즉 모든 $1\le i\le N$에 대해 $P_i$ = Uncolored이다.

한 번의 붓질로 세 가지 원색 중 하나를 골라 연속한 정사각형들에 칠할 수 있다. 다시 말해 색 $c$와 두 정수 $l$, $r$을 골라 $1\le l\le r\le N$을 만족할 때, $l\le j\le r$인 모든 정사각형 $P_j$에 색 $c$를 칠할 수 있다. 칠하려는 정사각형이 현재 Uncolored이면 색이 $c$가 된다. 그렇지 않으면 위 목록에 따라 지금까지 이 정사각형에 칠해진 모든 색과 새 색 $c$의 조합이 된다.

시간을 아끼기 위해 붓질 횟수를 최소로 하고 싶다. 그리고자 하는 그림의 설명이 주어질 때, 그림을 완성하는 데 필요한 최소 붓질 횟수를 구하라.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. $T$개의 테스트 케이스가 이어진다.

각 테스트 케이스는 그림의 길이를 나타내는 정수 $N$이 있는 줄로 시작한다. 다음 줄에는 그림을 나타내는 길이 $N$의 문자열 $P$가 주어진다. $i$번째 문자는 다음 목록에 따라 정사각형 $P_i$의 색을 나타낸다.

• U = Uncolored
• R = Red
• Y = Yellow
• B = Blue
• O = Orange
• P = Purple
• G = Green
• A = Gray

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 그림을 완성하는 데 필요한 최소 붓질 횟수이다.

• $1\le T\le 100$.
• $1\le N\le 10^5$.