// Arup Guha
// 6/24/2025
// Eight-Puzzle

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

// MOVES[i] stores which pieces we can swap index i with in our string.
const vector<vector<int>> MOVES = { {1,3}, {0,2,4}, {1,5}, {0,4,6}, {1,3,5,7}, {2,4,8},
                                    {3,7},{4,6,8},{5,7}};

vector<string> getNext(string& cur);

int main() {

    // My distance map.
    map<string,int> dist;
    dist["123456780"] = 0;

    // My queue.
    queue<string> q;
    q.push("123456780");

    // Run BFS.
    while (q.size() > 0) {

        // Get next.
        string cur = q.front(); q.pop();

        // Get all possible boards I could go to.
        vector<string> next = getNext(cur);

        // Go through each next board.
        for (string x: next) {

            // We've been here before.
            if (dist.count(x) > 0) continue;

            // Update distance and add to queue.
            dist[x] = dist[cur] + 1;
            q.push(x);
        }
    }

    int nC;
    cin >> nC;

    //  Process cases.
    for (int loop=0; loop<nC; loop++) {

        // Read in the input string.
        string inp="";
        for (int i=0; i<9; i++) {
            string tmp;
            cin >> tmp;
            inp = inp + tmp;
        }

        // Ta da!
        cout << dist[inp] << endl;
    }

    return 0;
}

// Returns all possible reachable board states from cur in one move.
vector<string> getNext(string& cur) {

    // Need to find 0 index.
    int idx = -1;
    for (int i=0; i<cur.size(); i++)
        if (cur[i] == '0')
            idx = i;

    vector<string> res;

    // Go through each index I could swap idx with.
    for (int newidx : MOVES[idx]) {
        swap(cur[idx], cur[newidx]);
        res.push_back(string(cur));
        swap(cur[idx], cur[newidx]);
    }

    // Ta da!
    return res;
}