다시 우주 구하기

외계 로봇이 모든 알고리즘 지식을 파괴할 광선을 사용하여 우주를 위협하고 있다. 우리는 이를 막아야 한다!

다행히도 우리는 로봇이 어떻게 작동하는지 알고 있다. 로봇은 세기가 1인 광선으로 시작하며, 일련의 명령으로 이루어진 프로그램을 실행한다. 명령은 왼쪽에서 오른쪽 순서로 하나씩 실행된다. 각 명령은 다음 두 유형 중 하나이다.

• C ("충전"을 뜻함): 광선의 세기를 두 배로 만든다.

• S ("발사"를 뜻함): 광선을 발사하여 광선의 현재 세기와 같은 피해를 준다.

예를 들어 로봇의 프로그램이 SCCSSC라면, 프로그램이 실행될 때 로봇은 다음과 같이 행동한다.

• 광선을 발사하여 1의 피해를 준다.

• 광선을 충전하여 광선의 세기를 2로 두 배 증가시킨다.

• 광선을 충전하여 광선의 세기를 4로 두 배 증가시킨다.

• 광선을 발사하여 4의 피해를 준다.

• 광선을 발사하여 4의 피해를 준다.

• 광선을 충전하여 광선의 세기를 8로 증가시킨다.

이 경우 프로그램은 총 9의 피해를 준다.

우주 최고의 알고리즘 전문가들은 최대 총 D의 피해를 견딜 수 있는 방어막을 개발했다. 하지만 로봇의 현재 프로그램은 실행될 때 그보다 더 큰 피해를 줄 수도 있다.

우주 대통령은 로봇이 프로그램을 실행하기 전에 우주로 날아가 로봇의 프로그램을 해킹하겠다고 자원했다. 대통령이 로봇에게 들키지 않고 해킹할 수 있는 유일한 방법은 인접한 두 명령의 위치를 맞바꾸는 것이다. 예를 들어 대통령은 위 프로그램의 세 번째 명령과 네 번째 명령을 맞바꾸는 해킹을 한 번 수행하여 프로그램을 SCSCSC로 만들 수 있다. 그러면 총피해가 7로 줄어든다. 그다음 예를 들어 대통령은 프로그램을 다시 해킹하여 SCSSCC로 만들어 피해를 5로 줄일 수 있으며, 이런 식으로 계속할 수 있다.

로봇이 지나치게 의심하지 않도록 대통령은 너무 많이 해킹하고 싶지 않다. 가능하다면 프로그램이 총 D 이하의 피해를 주도록 보장하는 데 필요한 최소 해킹 횟수는 얼마인가?

제한

1 ≤ T ≤ 100. 1 ≤ D ≤ $10^{9}$. 2 ≤ P의 길이 ≤ 30. P의 모든 문자는 C 또는 S이다. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

로봇의 프로그램에는 C 문자가 없거나 하나만 포함된다.

테스트 세트 2 (비공개)

제한 절에 명시된 것 외에 추가 제한은 없다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 D와 문자열 P를 포함하는 한 줄로 이루어진다. D는 방어막이 견딜 수 있는 최대 총피해이고, P는 로봇의 프로그램이다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 목표를 달성하는 데 필요한 최소 해킹 횟수 또는 달성이 불가능한 경우 IMPOSSIBLE이다.

마지막 세 예제 케이스는 테스트 세트 1에 등장하지 않는다는 점에 유의하라.

예제 케이스 #1에서 대통령은 두 명령의 위치를 맞바꾸어 총피해를 방어막이 견딜 수 있는 1로 줄일 수 있다.

예제 케이스 #2에서는 방어막이 프로그램으로 인해 발생할 총피해 2를 이미 견딜 수 있으므로 대통령이 프로그램을 전혀 해킹할 필요가 없다.

예제 케이스 #3에서 프로그램은 방어막이 견딜 수 있는 것보다 더 큰 피해를 주며, 해킹해도 이를 바꿀 수 없다. 우주는 끝장이다.

예제 케이스 #4에서는 문제 설명에 나온 프로그램을 사용한다. 문제 설명에는 두 번의 해킹을 사용하여 총피해를 5로 줄이는 한 가지 방법이 제시되어 있다. 단 한 번의 해킹만 사용해서 피해를 6 이하로 줄이는 것은 불가능하다. 대통령은 인접한 명령끼리만 위치를 맞바꿀 수 있음을 기억하라.

예제 케이스 #5에서 로봇은 절대로 광선을 발사하지 않으므로 어떠한 피해도 주지 않는다. 해킹은 필요하지 않다.

예제 케이스 #6에서는 다섯 번의 해킹이 필요하다. 두 번의 해킹에서 같은 두 위치의 명령을 맞바꾸더라도 별개의 해킹으로 센다는 점에 유의하라.