悬一关，可恶的90pts

//有很多人双向bfs也能通过啊（题解区的）， 请问我的为什么不可以啊
#include <bits/stdc++.h>
using namespace std;
int t;
string sstart = "", send = "111110111100*110000100000";
int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
queue<string> qstart, qend; 
unordered_map<string, int> mp1, mp2;

void bfs() {
    qstart.push(sstart); qend.push(send);
    mp1[sstart] = 0; mp2[send] = 0;
    while(qstart.size() && qend.size()) {
        if (qstart.size() > qend.size()) {
            swap(qstart, qend);
            swap(mp1, mp2);
        }
        auto q = qstart.front();
        qstart.pop();
        if (mp2.count(q)) {
            int ans = mp1[q] + mp2[q];
            cout << (ans <= 10 ? ans : -1) << '\n';
            return;
        }
        int position = q.find("*");
        int x = position / 5, y = position % 5;
        for (int i = 0; i < 8; i ++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
                auto t = q;
                swap(t[nx * 5 + ny], t[x * 5 + y]);
                if (!mp1.count(t)) {
                    mp1[t] = mp1[q] + 1;
                    qstart.push(t);
                }
            }
        }
    }
    cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while (t --) {
        sstart = "";
        while (qstart.size()) {
            qstart.pop();
        }
        while (qend.size()) {
            qend.pop();
        }
        mp1.clear();
        mp2.clear();
        string ch;
        for (int i = 1; i <= 5; i ++) {
            cin >> ch;
            sstart += ch;
        }
        bfs();
    }
    return 0;
}