#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
using namespace std;

int p, dist[5050], par[5050];
map<int, int> shortCode;
vector<int> longCode, g[5050];

int vertex(char *s) {
    int code = 0;
    for (int i = 0; i < 7; i++)
        code = code * 10 + (s[i] == '0' ? 0 : s[i] - 'A' + 1);
    map<int, int>:: iterator r = shortCode.find(code);
    if (r != shortCode.end())
        return r->second;
    longCode.push_back(code);
    shortCode.insert(make_pair(code, longCode.size() - 1));
    return longCode.size() - 1;
}

void buildEdges(char *s) {
    int z, e1 = -1, e2 = -1, e3 = -1;
    for (z = 0; s[z] != '0'; z++);
    switch (z) {
        case 0: e1 = 1; e2 = 5; break;
        case 1: e1 = 0; e2 = 2; e3 = 6; break;
        case 2: e1 = 1; e2 = 3; break;
        case 3: e1 = 2; e2 = 4; break;
        case 4: e1 = 3; e2 = 5; e3 = 6; break;
        case 5: e1 = 0; e2 = 4; break;
        case 6: e1 = 1; e2 = 4; break;
    }
    int v = vertex(s);
    swap(s[z], s[e1]);
    g[v].push_back(vertex(s));
    swap(s[z], s[e1]);
    swap(s[z], s[e2]);
    g[v].push_back(vertex(s));
    swap(s[z], s[e2]);
    if (e3 != -1) {
        swap(s[z], s[e3]);
        g[v].push_back(vertex(s));
        swap(s[z], s[e3]);
    }
}

char movedLetter(int v1, int v2) {
    int state1 = longCode[v1], state2 = longCode[v2];
    while (state1 % 10 != 0) {
        state1 /= 10;
        state2 /= 10;
    }
    return 'A' - 1 + state2 % 10;
}

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

    char s[10] = "ABCDEF0";
    sort(s, s + 7);
    buildEdges(s);
    while (next_permutation(s, s + 7))
        buildEdges(s);

    queue<int> q;
    for (int i = 0; i < 5050; i++)
        dist[i] = par[i] = -1;
    dist[vertex("ABCDEF0")] = 0;
    q.push(vertex("ABCDEF0"));
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int i = 0; i < g[v].size(); i++) {
            if (dist[g[v][i]] == -1) {
                par[g[v][i]] = v;
                dist[g[v][i]] = dist[v] + 1;
                q.push(g[v][i]);
            }
        }
    }

    scanf("%d", &p);
    for (int tst = 1; tst <= p; tst++) {
        scanf("%*d %s", s);
        int v = vertex(strcat(s, "0"));
        if (dist[v] == -1) {
            printf("%d NO SOLUTION\n", tst);
            continue;
        }
        printf("%d %d ", tst, dist[v]);
        while (par[v] != -1) {
            printf("%c", movedLetter(v, par[v]));
            v = par[v];
        }
        printf("\n");
    }

    return 0;
}