화가

당신은 최근 그림 그리는 법을 배우기 시작했으며, 첫 수업 중 하나에서 세 가지 원색인 빨강, 노랑, 파랑을 배웠다. 이 색들을 조합하면 훨씬 더 많은 색을 만들 수 있다. 지금까지 배운 조합은 다음과 같다.

• 빨강 + 노랑 = 주황

• 빨강 + 파랑 = 보라

• 노랑 + 파랑 = 초록

• 빨강 + 노랑 + 파랑 = 회색

아직 색의 농담을 이해하지 못하므로, 조합에서 각 색의 비율과 순서는 중요하지 않다. 예를 들어 빨강과 노랑을 조합한 결과는 노랑과 빨강을 조합한 결과와 같으며, 빨강, 노랑, 그리고 빨강을 다시 조합한 결과와도 같다.

기술을 연습하기 위해 길이 $\mathbf{N}$인 1차원 그림 $\mathbf{P}$를 칠하려고 한다. 그림은 $\mathbf{N}$개의 정사각형으로 이루어진다. 왼쪽부터 오른쪽으로, $\mathbf{P_i}$는 i번째 정사각형의 색을 나타낸다. 처음에는 모든 정사각형이 색칠되지 않은 상태이다. 즉, 모든 $1 \le i \le \mathbf{N}$에 대해 $\mathbf{P_i}$ = 색칠되지 않음이다.

한 번의 붓질로 세 가지 원색 중 하나를 골라 연속한 정사각형들에 칠할 수 있다. 다시 말해, $1 \le l \le r \le \mathbf{N}$를 만족하도록 색 $c$와 두 정수 $l$, $r$를 고르고, $l \le j \le r$를 만족하는 모든 정사각형 $\mathbf{P_j}$에 색 $c$를 칠할 수 있다. 칠하려는 정사각형이 현재 색칠되지 않은 상태라면 그 색은 $c$가 된다. 그렇지 않다면 위 목록에서 설명한 대로, 그 정사각형에 지금까지 칠한 모든 색과 새로운 색 $c$를 조합한 색이 된다.

시간을 절약하기 위해 가능한 한 적은 횟수로 붓질하려고 한다. 칠하려는 그림에 대한 설명이 주어질 때, 그림을 칠하는 데 필요한 최소 붓질 횟수를 구한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 10^5$.

테스트 세트 1

시간 제한: 20초. $\mathbf{P_i}$는 {Y, B, G} 중 하나이다.

테스트 세트 2

시간 제한: 40초. $\mathbf{P_i}$는 {U, R, Y, B, O, P, G, A} 중 하나이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

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

• U = 색칠되지 않음

• R = 빨강

• Y = 노랑

• B = 파랑

• O = 주황

• P = 보라

• G = 초록

• A = 회색

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

예제 케이스 #1의 해법은 $3$번 붓질하는 것이다. 첫 번째 붓질은 정사각형 $1$부터 $3$까지 노랑으로 칠하고, 두 번째 붓질은 정사각형 $4$부터 $6$까지 파랑으로 칠하며, 세 번째 붓질은 정사각형 $7$부터 $9$까지 노랑으로 칠한다. 이 그림에는 원색만 필요했다는 점에 유의한다.

예제 케이스 #2의 해법은 $2$번 붓질하는 것이다. 첫 번째 붓질은 정사각형 $1$부터 $4$까지 노랑으로 칠하고, 두 번째 붓질은 정사각형 $3$부터 $6$까지 파랑으로 칠한다. 정사각형 $3$와 $4$는 노랑과 파랑 두 색으로 모두 칠해지며, 그 결과 초록이 된다는 점에 유의한다.

추가 예제 - 테스트 세트 2

예제 케이스 #3의 해법은 $3$번 붓질하는 것이다. 첫 번째 붓질은 정사각형 $1$부터 $5$까지 빨강으로 칠하고, 두 번째 붓질은 정사각형 $2$부터 $4$까지 노랑으로 칠하며, 세 번째 붓질은 정사각형 $3$을 파랑으로 칠한다. 정사각형 $3$은 세 가지 원색으로 모두 칠해지며, 그 결과 회색이 된다는 점에 유의한다.