UVa Q704

//UVa Q704
#include <bits/stdc++.h>
using namespace std;

string lr(string in){//s.size() := 24
    string s = in;
    char a = s[10], b = s[11];
    for(int i = 11; i >= 2; --i)s[i] = s[i-2];
    s[0] = a; s[1] = b;
    for(int i = 21; i <= 23; ++i)s[i] = s[i-12];
    return s;
}
string rr(string in){//s.size() := 24
    string s = in;
    char a = s[12], b = s[13];
    for(int i = 12; i <= 21; ++i)s[i] = s[i+2];
    s[22] = a; s[23] = b;
    for(int i = 9; i <= 11; ++i)s[i] = s[i+12];
    return s;
}
string ll(string in){//s.size() := 24
    string s = in;
    char a = s[0], b = s[1];
    for(int i = 0; i <= 9; ++i)s[i] = s[i+2];
    s[10] = a; s[11] = b;
    for(int i = 21; i <= 23; ++i)s[i] = s[i-12];
    return s;
}
string rl(string in){//s.size() := 24
    string s = in;
    char a = s[22], b = s[23];
    for(int i = 23; i >= 14; --i)s[i] = s[i-2];
    s[12] = a; s[13] = b;
    for(int i = 9; i <= 11; ++i)s[i] = s[i+12];
    return s;
}
string (*turn[])(string in) = {nullptr, lr, rr, ll, rl};

map<string, string> V, U;
string ans;

void dfs1(int depth, string s, string vs){
    V[s] = vs;
    //cout << depth << ' ' << s << ' ' << vs << endl;
    if(depth >= 8)return;
    for(int i = 1; i <= 4; ++i){
        string x = turn[i](s);
        if(V.find(x) == V.end() || V[x].size() > vs.size()+1LL){
            dfs1(depth+1, x, (char)((i+1)%4+'1') + vs);
        }
    }
}

void dfs2(int depth, string s, string us){
    U[s] = us;
    if(V.find(s) != V.end() && ans.size() > us.size() + V[s].size())ans = us + V[s];
    //cout << depth << ' ' << s << ' ' << us << endl;
    if(depth >= 8)return;
    for(int i = 1; i <= 4; ++i){
        string x = turn[i](s);
        if(U.find(x) == U.end() || U[x].size() > us.size()+1LL){
            dfs2(depth+1, x, us + (char)(i+'0'));
        }
    }
}

int main(){
    int t,x;
    string tar = "034305650121078709:90121";
    dfs1(0, tar, "");
    cin >> t;
    while(t--){
        U.clear();
        ans = "000000000000000000000000";
        string s;
        for(int i = 0; i < 24; ++i){
            cin >> x;
            s += char(x+'0');
        }
        if(s == tar)cout << "PUZZLE ALREADY SOLVED\n";
        else if(V.find(s) != V.end())cout << V[s] << endl;
        else{
            dfs2(0, s, "");
            if(ans.size() <= 16)cout << ans << '\n';
            else cout << "NO SOLUTION WAS FOUND IN 16 STEPS\n";
        }
    }
    return 0;
}