Một robot ngoài hành tinh đang đe dọa vũ trụ bằng một tia năng lượng có thể phá hủy toàn bộ tri thức về thuật toán. Chúng ta phải ngăn nó lại!

May thay, chúng ta hiểu cách robot hoạt động. Ban đầu tia có sức mạnh 1. Robot chạy một chương trình gồm một chuỗi lệnh, được thực thi lần lượt từ trái sang phải. Mỗi lệnh thuộc một trong hai loại:

• C (viết tắt của “charge”, nạp năng lượng): nhân đôi sức mạnh của tia.

• S (viết tắt của “shoot”, bắn): bắn tia và gây lượng sát thương bằng sức mạnh hiện tại của tia.

Ví dụ, nếu chương trình của robot là SCCSSC, khi chạy chương trình robot sẽ thực hiện như sau:

• Bắn tia, gây 1 sát thương.
• Nạp năng lượng, nhân đôi sức mạnh của tia thành 2.
• Nạp năng lượng, nhân đôi sức mạnh của tia thành 4.
• Bắn tia, gây 4 sát thương.
• Bắn tia, gây 4 sát thương.
• Nạp năng lượng, tăng sức mạnh của tia thành 8.

Trong trường hợp đó, chương trình gây tổng cộng 9 sát thương.

Các nhà thuật toán hàng đầu của vũ trụ đã phát triển một tấm khiên chịu được tổng sát thương tối đa là \(D\). Tuy nhiên, chương trình hiện tại của robot có thể gây nhiều sát thương hơn mức đó khi được chạy.

Tổng thống Vũ trụ tình nguyện bay vào không gian để hack chương trình trước khi robot chạy nó. Cách duy nhất Tổng thống có thể hack mà không bị robot phát hiện là đổi chỗ hai lệnh kề nhau. Chẳng hạn, Tổng thống có thể hack chương trình trên một lần bằng cách đổi lệnh thứ ba và thứ tư, tạo thành SCSCSC và giảm tổng sát thương xuống 7. Sau đó, ví dụ, Tổng thống có thể hack thêm lần nữa để được SCSSCC, giảm sát thương xuống 5, và cứ thế tiếp tục.

Để robot không nghi ngờ quá mức, Tổng thống không muốn hack quá nhiều lần. Nếu có thể làm cho chương trình gây tổng sát thương không quá \(D\), số lần hack nhỏ nhất cần dùng là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số lượng test \(T\). Mỗi test tiếp theo gồm một dòng chứa số nguyên \(D\) và chuỗi \(P\): tổng sát thương tối đa tấm khiên chịu được và chương trình của robot.

Dữ liệu ra

Với mỗi test, in một dòng Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1; y là số lần hack nhỏ nhất để đạt mục tiêu, hoặc IMPOSSIBLE nếu không thể.

Ràng buộc

• \(1\le T\le100\).
• \(1\le D\le10^9\).
• \(2\le |P|\le30\).
• Mỗi ký tự của \(P\) là C hoặc S.

Phân nhóm

Test Set 1 (công khai): chương trình của robot chứa không quá một ký tự C.

Test Set 2 (ẩn): không có ràng buộc bổ sung ngoài các ràng buộc chung.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

6
1 CS
2 CS
1 SS
6 SCCSSC
2 CC
3 CSCSS

Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 2
Case #5: 0
Case #6: 5

Nguồn

Google Code Jam 2018, Vòng loại, bài Saving The Universe Again.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.