#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>

using namespace std;

typedef long long ll; typedef unsigned long long ull; typedef vector<ll> vi; typedef pair<ll,ll> pi;
const int _1e5 = 100000; const int _1e7 = 10000000; const int _1e9 = 1000000000;

template<typename A, typename B> ostream& operator<<(ostream& str, const pair<A,B>& p) { return str << "(" << p.first << ", " << p.second << ")"; }
template<typename T> ostream& operator<<(ostream& str,             const vector<T>& v) { str << "["; for(const auto& n : v) str << n << ", "; str << "]"; return str; }
template<typename T> ostream& operator<<(ostream& str,             const set<T>& v) { str << "{"; for(const auto& n : v) { str << n << ", "; } str << "}"; return str; }
template<typename K, typename V> ostream& operator<<(ostream& str, const unordered_map<K, V>& v) { str << "{"; for(const auto& p : v) { str << p.first << " => " << p.second << ", "; } str << "}"; return str; }

#define debug(x) cout <<  #x  << ": " << x << endl


int main() {
	ios_base::sync_with_stdio(false);

	int cases; cin >> cases;

	for (int case_=1; case_<=cases; ++case_) {
		long long d; cin >> d;
		string p; cin >> p;

		std::priority_queue<int, vector<int>, std::greater<int>> q;
		long long damage = 1;
		long long total = 0;

		for (char c : p) {
			if (c == 'S') {
				total += damage;
				if (damage > 1) {
					q.push(damage);
				}
			} else {
				damage *= 2;
			}
		}

		int hacks = 0;
		while (total > d && !q.empty()) {
			int top = q.top();
			q.pop();

			top /= 2;
			hacks += 1;
			total -= top;

			if (top > 1) {
				q.push(top);
			}
		}

		cout << "Case #" << case_ << ": ";
		if (total <= d) {
			cout << hacks << '\n';
		} else {
			cout << "IMPOSSIBLE\n";
		}
	}
}