#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;

const long long MOD = 1e9 + 7;

long long f(const string &s) {
    vector<long long> l(s.size()), r(s.size());
    l[0] = s[0] == 'O';
    r[0] = s[0] == 'X';

    for (int i = 1; i < s.size(); i++) {
        if (s[i] == 'X') {
            l[i] = min(l[i - 1], r[i - 1] + 1);
            r[i] = min(l[i - 1] + 1, r[i - 1] + 2);
        } else if (s[i] == 'F') {
            l[i] = min(l[i - 1], r[i - 1] + 1);
            r[i] = min(l[i - 1] + 1, r[i - 1]);
        } else {
            l[i] = min(l[i - 1] + 2, r[i - 1] + 1);
            r[i] = min(l[i - 1] + 1, r[i - 1]);
        }
    }

    auto res = min(l.back(), r.back());

    return res;
}

long long gNaive(const string &s) {
    long long res = 0;
    for (int l = 0; l < s.size(); l++)
        for (int r = l; r < s.size(); r++)
            res = (res + f(s.substr(l, r - l + 1))) % MOD;
    return res;
}

long long g(const string &s) {
    vector<pair<int, int>> pos;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'X')
            pos.push_back({ 1, i });
        if (s[i] == 'O')
            pos.push_back({ 2, i });
    }

    long long res = 0;

    for (int i = 1; i < pos.size(); i++) {
        if (pos[i - 1].first == pos[i].first)
            continue;

        long long l = pos[i - 1].second + 1;
        long long r = s.size() - pos[i].second;

        res = (res + l * r % MOD) % MOD;
    }

    return res;
}

string generateString(int size, int n) {
    string letters = "FOX";
    string res;
    for (int i = 0; i < size; i++) {
        res += letters[n % 3];
        n /= 3;
    }
    return res;
}

void testG() {
    for (int size = 1, limit = 3; size <= 10; size++, limit *= 3) {
        for (int n = 0; n < limit; n++) {
            string s = generateString(size, n);

            long long res = g(s);
            long long resNaive = gNaive(s);

            if (res != resNaive) {
                cout << s << "\n";
                cout << res << "\n";
                cout << resNaive << "\n";
                return;
            }
        }
    }

    cerr << "Max test:";
    for (int i = 0; i < 5; i++) {
        string s = generateString(4e6, rand() * rand());
        long long res = g(s);
        cerr << res << "\n";
    }
}

void solve(int test) {
    int n;
    string s;
    cin >> n >> s;

    cout << "Case #" << test << ": " << g(s) << "\n";
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    //testG();

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int test = 1; test <= n; test++)
        solve(test);
}