우주를 다시 구하기

외계 로봇이 모든 알고리즘 지식을 파괴하는 빔으로 우주를 위협하고 있습니다. 이 로봇을 막아야 합니다.

다행히 로봇의 동작 원리는 알려져 있습니다. 로봇은 세기가 1인 빔으로 시작하며, 명령어들로 이루어진 프로그램을 왼쪽에서 오른쪽 순서로 한 번에 하나씩 실행합니다. 각 명령어는 다음 두 종류 중 하나입니다.

• C (charge): 빔의 세기를 두 배로 만듭니다.
• S (shoot): 빔을 발사하여, 현재 빔의 세기만큼 피해를 줍니다.

예를 들어 프로그램이 SCCSSC이면 로봇은 다음과 같이 동작합니다.

• 빔을 발사하여 1의 피해를 줍니다.
• 빔을 충전하여 세기가 2가 됩니다.
• 빔을 충전하여 세기가 4가 됩니다.
• 빔을 발사하여 4의 피해를 줍니다.
• 빔을 발사하여 4의 피해를 줍니다.
• 빔을 충전하여 세기가 8이 됩니다.

이 경우 프로그램이 주는 총 피해는 9입니다.

우주 최고의 알고리즘 연구자들은 총 $D$의 피해까지만 견딜 수 있는 방패를 개발했습니다. 하지만 로봇의 현재 프로그램은 실행 시 그보다 더 큰 피해를 줄 수 있습니다.

우주의 대통령은 로봇이 프로그램을 실행하기 전에 우주선을 타고 올라가 프로그램을 해킹하려 합니다. 로봇에게 들키지 않고 할 수 있는 해킹은 인접한 두 명령어를 서로 바꾸는 것뿐입니다. 예를 들어 위 프로그램의 3번째와 4번째 명령어를 바꾸면 SCSCSC가 되고 총 피해는 7로 줄어듭니다. 여기서 다시 해킹하여 SCSSCC로 만들면 피해는 5로 줄어듭니다.

대통령은 해킹 횟수를 많이 늘리고 싶지 않습니다. 프로그램의 총 피해를 $D$ 이하로 만드는 해킹 횟수의 최솟값을 구하세요. 그런 방법이 없다면 그 사실을 알려야 합니다.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 줄이 주어지며, 각 줄에는 방패가 견딜 수 있는 최대 총 피해 $D$와 로봇의 프로그램인 문자열 $P$가 주어집니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력합니다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 필요한 해킹 횟수의 최솟값입니다. 어떤 횟수로도 목표를 달성할 수 없으면 $y$ 자리에 IMPOSSIBLE을 출력합니다.

• $1 \le T \le 100$
• $1 \le D \le 10^9$
• $2 \le |P| \le 30$
• $P$의 모든 문자는 C 또는 S입니다.

마지막 세 개의 샘플 케이스는 테스트 세트 1에는 나타나지 않습니다.

샘플 케이스 #1에서 대통령은 두 명령어를 바꿔 총 피해를 1로 줄일 수 있으며, 방패가 이를 견딜 수 있습니다.

샘플 케이스 #2에서는 프로그램이 일으키는 총 피해가 2이고 방패가 이를 이미 견디므로 해킹이 필요하지 않습니다.

샘플 케이스 #3에서는 프로그램이 방패가 견딜 수 있는 양보다 많은 피해를 줍니다. 해킹으로는 이를 바꿀 수 없습니다. 우주는 멸망합니다.

샘플 케이스 #4는 문제 설명의 프로그램을 사용합니다. 해킹 2회로 피해를 5로 줄일 수 있습니다. 대통령은 인접한 명령어만 교환할 수 있으므로, 해킹 1회로는 피해를 6 이하로 줄일 수 없습니다.

샘플 케이스 #5에서는 로봇이 발사하지 않으므로 피해가 없습니다. 해킹은 필요하지 않습니다.

샘플 케이스 #6에서는 해킹이 다섯 번 필요합니다. 같은 두 위치를 바꾸는 해킹이라도 각각 별개의 해킹으로 셉니다.