#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loopf(i, a, b) for (int i = a; i < b; i++)
#define loopb(i, a, b) for (int i = a; i > b; i--)
#define pb push_back
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define ff first
#define ss second
#define vc vector
#define vii vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mapii map<int, int>
#define mapll map<ll, ll>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define ld long double
#define sz(v) (int)(v.size())
#define len(v) (int)(v.length())
const ll M = 1e9 + 7;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
        cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
        cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif

#define yes1 cout << "YES" << endl
#define no1 cout << "NO" << endl
#define yes2 cout << "Yes" << endl
#define no2 cout << "N0" << endl
#define imax INT_MAX
#define imin INT_MIN
#define lmax LLONG_MAX
#define lmin LLONG_MIN

class node
{
public:
    int val;
    node *prev;
    node *next;
    node()
    {
        prev = next = NULL;
    }
    node(node *prev, node *next, int val)
    {
        this->next = next;
        this->prev = prev;
        this->val = val;
    }

    int length()
    {
        int cnt = 0;
        node *temp = this;
        while (temp)
        {
            cnt++;
            temp = temp->next;
        }
        return cnt;
    }

    void print()
    {
        node *temp = this;
        while (temp)
        {
            cout << temp->val;
            temp = temp->next;
        }
        cout << endl;
    }
};

node *head;
node *last;

void insert(node *n)
{
    if (head == NULL)
    {
        head = n;
        last = n;
        return;
    }

    n->prev = last;
    last->next = n;
    last = last->next;
}

void solve()
{
    int n;
    cin >> n;

    string s;
    cin >> s;

    head = NULL;
    last = NULL;

    loopf(i, 0, n)
    {
        node *temp = new node(NULL, NULL, s[i] - '0');
        insert(temp);
    }

    unordered_set<node *> v[10];

    node *ptr = head;

    int prev_len = head->length();

    while (ptr->next)
    {
        if (ptr->next->val == (ptr->val + 1) % 10)
        {
            v[ptr->val].insert(ptr);
        }
        ptr = ptr->next;
    }

    unordered_map<node*,bool> taken;

    while (true)
    {

        // debug("YES");

        for (int i = 0; i < 10; i++)
        {
            // debug(sz(v[i]));
            while (sz(v[i]) > 0)
            {
                node *curr = *(v[i].begin());
                v[i].erase(v[i].begin());

                if ( taken[curr]==false &&  curr->next && (curr->val + 1) % 10 == curr->next->val)
                {
                    taken[curr->next]=true;
                    curr->next = curr->next->next;
                    if (curr->next)
                        curr->next->prev = curr;
                }
                else
                    continue;

                curr->val = (curr->val + 2) % 10;

                if (curr->prev)
                {
                    if ((curr->prev->val + 1) % 10 == curr->val)
                    {
                        v[curr->prev->val].insert(curr->prev);
                    }
                }
                if (curr->next)
                {
                    if ((curr->val + 1) % 10 == curr->next->val)
                    {
                        v[curr->val].insert(curr);
                    }
                }
            }
            // head->print();
        }

        if (prev_len == head->length())
            break;
        prev_len = head->length();
    }

    head->print();
}

int main()
{
    int t;
    t = 1;
    cin >> t;
    loopf(i, 0, t)
    {
        cout << "Case #" << i + 1 << ": ";
        solve();
    }
}