34623번 - 가위바위보

문제

R, S, P로 이루어진 길이 $N$의 문자열 $S$가 주어진다. 이때 R, S, P는 각각 바위, 가위, 보를 뜻하는 문자이다. 하늘이는 다음과 같은 가위바위보 연산을 여러 번 수행할 수 있다.

• 가위바위보 연산: $S$에서 서로 다른 인접한 두 문자를 골라 이기는 쪽으로 두 문자를 모두 대체한다.

구체적으로,

• R과 S를 골랐다면 두 문자를 모두 R로 대체한다.
• S와 P를 골랐다면 두 문자를 모두 S로 대체한다.
• P와 R을 골랐다면 두 문자를 모두 P로 대체한다.

하늘이는 다음의 세 가지 값을 구하려고 한다.

1. 문자열의 모든 문자를 R로 만드는 데 필요한 최소 연산 횟수 (불가능하다면 $-1$)
2. 문자열의 모든 문자를 S로 만드는 데 필요한 최소 연산 횟수 (불가능하다면 $-1$)
3. 문자열의 모든 문자를 P로 만드는 데 필요한 최소 연산 횟수 (불가능하다면 $-1$)

연산은 임의의 순서로 반복할 수 있으며, 각 목표에 대해서 독립적으로 최적의 연산 수를 계산하면 된다.

하나의 입력 데이터에서 $T$개의 테스트케이스를 해결해야 한다.

입력

첫째 줄에 테스트케이스의 개수 $T$가 주어진다. (1ドル \leq T \leq 10^6$)

다음 줄부터 $T$개의 테스트케이스가 입력으로 주어진다.

각각의 테스트케이스는 다음의 두 줄로 이루어진다.

• 첫째 줄에 정수 $N$이 주어진다. (1ドル \leq N \leq 10^6$)
• 둘째 줄에 R, S, P로 이루어진 길이 $N$의 문자열 $S$가 주어진다.

이때 각 테스트케이스의 $N$을 모두 더한 값은 10ドル^6$을 넘지 않는다.

출력

$T$개의 줄에 순서대로 각 테스트케이스의 정답을 출력한다.

각 줄에는 세 정수를 공백으로 구분하여 출력한다. 세 정수는 순서대로 다음을 의미한다.

1. $S$의 모든 문자를 R로 만드는 데 필요한 최소 연산 횟수 (불가능하다면 $-1$)
2. $S$의 모든 문자를 S로 만드는 데 필요한 최소 연산 횟수 (불가능하다면 $-1$)
3. $S$의 모든 문자를 P로 만드는 데 필요한 최소 연산 횟수 (불가능하다면 $-1$)

제한

노트