import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine().trim());
        int[][] coord = {{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}};
        long value;
        long board = (1L << 36) - 1;
        long answer = 0;
        long cur = 0, check;
        long oneCount = ((2L << 50) + (2L << 40));
        int r, c, nr, nc, index, num;
        int[][] d = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        for(long i = 1; i < 9; i++) {
            answer |= i << ((i - 1) * 4);
        }
        Set<Long> impossible = new HashSet<>();
        Set<Long> tmp = new HashSet<>();
        Set<Long> set = new HashSet<>();
        char[][] arr = new char[3][3];
        boolean im;
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
        StringBuilder stringBuilder = new StringBuilder();
        for(int t = 1; t <= n; t++) {
            bufferedReader.readLine();
            arr[0] = bufferedReader.readLine().trim().toCharArray();
            arr[1] = bufferedReader.readLine().trim().toCharArray();
            arr[2] = bufferedReader.readLine().trim().toCharArray();
            value = 0;
            for(int i = 0; i < 3; i++) {
                for(int j = 0; j < 3; j++) {
                    if(arr[i][j] == '#') {
                        value += (long)(Math.abs(i - 2) + Math.abs(j - 2)) << 50;
                        value += ((long)(i * 3 + j) << 36);
                    } else {
                        value += (long)(Math.abs(i - coord[arr[i][j] - '1'][0]) + Math.abs(j - coord[arr[i][j] - '1'][1])) << 50;
                        value |= (long)((arr[i][j] - '0')) << ((i * 3 + j) * 4);
                    }
                }
            }
            tmp.clear();
            im = true;
            check = value & board;
            if(!impossible.contains(check)) {
                priorityQueue.clear();
                priorityQueue.offer(value);
                set.clear();
                set.add(check);
                tmp.add(check);
                im = false;
                while (!priorityQueue.isEmpty()) {
                    cur = priorityQueue.poll();
                    if ((cur & board) == answer) {
                        stringBuilder.append(cur >> 51).append('\n');
                        break;
                    }
                    int i = (int) ((cur >> 36) & 15L);
                    r = coord[i][0];
                    c = coord[i][1];
                    for (int j = 0; j < 4; j++) {
                        value = cur - ((long) (Math.abs(r - 2) + Math.abs(c - 2)) << 50);
                        nr = r + d[j][0];
                        nc = c + d[j][1];
                        if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3) {
                            index = nr * 3 + nc;
                            num = (int) ((cur >> (index * 4)) & 15) - 1;
                            value &= (~(15L << (index * 4)));
                            value |= ((long) (num + 1) << (i * 4));
                            check = value & board;
                            if(impossible.contains(check)) {
                                im = true;
                                break;
                            }
                            if (set.contains(check)) {
                                continue;
                            }
                            value += ((long) (Math.abs(nr - 2) + Math.abs(nc - 2)) << 50);
                            value -= ((long) (Math.abs(coord[num][0] - nr) + Math.abs(coord[num][1] - nc)) << 50);
                            value += ((long) (Math.abs(coord[num][0] - r) + Math.abs(coord[num][1] - c)) << 50);
                            value += oneCount;
                            value = ((value & ~(15L << 36)) | (((long) (nr * 3 + nc)) << 36));
                            set.add(check);
                            tmp.add(check);
                            priorityQueue.offer(value);
                        }
                    }
                    if(im) {
                        break;
                    }
                }
            }
            if(im || (cur & board) != answer) {
                impossible.addAll(tmp);
                stringBuilder.append("impossible\n");
            }
        }
        System.out.print(stringBuilder);
    }
}
