//12405 - Scarecrow (by Snail)
#include <iostream>
#include <string>
using namespace std;

int main () {
    string s;
    int t, n, tc=1, i;
    cin >> t;
    while (t--) {
        cin >> n >> s;
        int ns = 0;                             // no of s(carecrow)
        for (i=0; i<n; i++)
            if (s[i]=='.')
                ns++, i+=2;
        cout << "Case " << tc++ << ": " << ns << endl;
    }
}

//12289 - One-Two-Three (by Snail)
#include <iostream>
#include <string>
using namespace std;

int main () {
    string s;
    int n;
    cin >> n;
    while (n--) {
        cin >> s;
        if (s.size() == 5)
            cout << "3\n";
        else if ((s[0]=='o') + (s[1]=='n') + (s[2]=='e') >= 2)
            cout << "1\n";
        else
            cout << "2\n";
    }
}

//11398 - The Base-1 Number System (by Snail)
#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    while (cin >> s, s != "~") {
        int n = 0, f, l;
        do {
            l = s.size();
            if (--l == 0)                       // 1 個 0
                f = 1;                          // 設 f 為 1
            else if (--l == 0)                  // 2 個 0
                f = 0;                          // 設 f 為 0
            else
                while (l--)                     // l 個 f
                    n = n * 2 + f
        } while (cin >> s, s != "#");
        cout << n << endl;
    }
}

//12439 - February 29 (by Snail)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main () {
    string m;
    int d, y, t, ld, tc=1;
    char ch;
    cin >> t;
    while (t--) {
        cin >> m >> d >> ch >> y;               // 輸入起始日期
        if (m=="January" || m=="February")      // 起始日期當年包含閏日
            y--;                                // 該年閏日不能扣掉
        ld = -(y/4 - y/100 + y/400);            // 扣掉起始日期前的閏日數
        cin >> m >> d >> ch >> y;               // 輸入結束日期
        if (m=="January" || m=="February" && d<29)// 結束日期當年不含閏日
            y--;                                // 該年閏日不能列入計算
        ld += y/4 - y/100 + y/400;              // 加上結束日期前的閏日數
        cout << "Case " << tc++ << ": " << ld << endl;
    }
}

//10063 - Knuth's Permutation (by Snail)
#include <iostream>
#include <string>
using namespace std;

string s;

void knuth (string p) {
    if (p.size() == s.size())
        cout << p << endl;
    else
        for (unsigned i=0; i<=p.size(); i++)
            knuth (p.substr(0, i) + s[p.size()] + p.substr(i));
}           // 將 s 的下一字元依序插入 p 的每個空隙

int main () {
    for (int tc=0; cin >> s; tc++) {
        if (tc) cout << endl;                   // 測試資料間空一行
        knuth (s.substr(0, 1));                  // 插入第一個字元
    }
}

//12406 - Help Dexter (by Snail)
#include <iostream>
#include <string>
using namespace std;

int main () {
    int t, p, q, tc=1;
    int r[18] = {0, 1, 2, 4, 6, 5, 8, 7, 11, 9, 10, 11, 12, 13, 17, 15, 16, 17};
    string s = "11211111212122112";             // 可以被 2^17 整除的 17 位數
    cin >> t;
    while (t--) {
        cin >> p >> q;
        cout << "Case " << tc++ << ": ";
        if (r[p] < q)                           // r[p]-- p 位數可被 2^r[p] 整除
            cout << "impossible\n";
        else {
            if (p <= q)
                cout << s.substr(17-p) << endl;
            else
                cout << string (p-q, '1') << s.substr (17-q) << ' '
                     << string (p-q, '2') << s.substr (17-q) << endl;
        }
    }
}