import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
public class Main {
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
); }
}
aW1wb3J0IGphdmEuaW8uQnVmZmVyZWRSZWFkZXI7CmltcG9ydCBqYXZhLmlvLklucHV0U3RyZWFtUmVhZGVyOwppbXBvcnQgamF2YS51dGlsLkhhc2hTZXQ7CmltcG9ydCBqYXZhLnV0aWwuUHJpb3JpdHlRdWV1ZTsKaW1wb3J0IGphdmEudXRpbC5TZXQ7CgpwdWJsaWMgY2xhc3MgTWFpbiB7CiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB0aHJvd3MgRXhjZXB0aW9uIHsKICAgICAgICBCdWZmZXJlZFJlYWRlciBidWZmZXJlZFJlYWRlciA9IG5ldyBCdWZmZXJlZFJlYWRlcihuZXcgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7CiAgICAgICAgaW50IG4gPSBJbnRlZ2VyLnBhcnNlSW50KGJ1ZmZlcmVkUmVhZGVyLnJlYWRMaW5lKCkudHJpbSgpKTsKICAgICAgICBpbnRbXVtdIGNvb3JkID0ge3swLCAwfSwgezAsIDF9LCB7MCwgMn0sIHsxLCAwfSwgezEsIDF9LCB7MSwgMn0sIHsyLCAwfSwgezIsIDF9LCB7MiwgMn19OwogICAgICAgIGxvbmcgdmFsdWU7CiAgICAgICAgbG9uZyBib2FyZCA9ICgxTCA8PCAzNikgLSAxOwogICAgICAgIGxvbmcgYW5zd2VyID0gMDsKICAgICAgICBsb25nIGN1ciA9IDAsIGNoZWNrOwogICAgICAgIGxvbmcgb25lQ291bnQgPSAoKDJMIDw8IDUwKSArICgyTCA8PCA0MCkpOwogICAgICAgIGludCByLCBjLCBuciwgbmMsIGluZGV4LCBudW07CiAgICAgICAgaW50W11bXSBkID0ge3swLCAxfSwgezEsIDB9LCB7LTEsIDB9LCB7MCwgLTF9fTsKICAgICAgICBmb3IobG9uZyBpID0gMTsgaSA8IDk7IGkrKykgewogICAgICAgICAgICBhbnN3ZXIgfD0gaSA8PCAoKGkgLSAxKSAqIDQpOwogICAgICAgIH0KICAgICAgICBTZXQ8TG9uZz4gaW1wb3NzaWJsZSA9IG5ldyBIYXNoU2V0PD4oKTsKICAgICAgICBTZXQ8TG9uZz4gdG1wID0gbmV3IEhhc2hTZXQ8PigpOwogICAgICAgIFNldDxMb25nPiBzZXQgPSBuZXcgSGFzaFNldDw+KCk7CiAgICAgICAgY2hhcltdW10gYXJyID0gbmV3IGNoYXJbM11bM107CiAgICAgICAgYm9vbGVhbiBpbTsKICAgICAgICBQcmlvcml0eVF1ZXVlPExvbmc+IHByaW9yaXR5UXVldWUgPSBuZXcgUHJpb3JpdHlRdWV1ZTw+KCk7CiAgICAgICAgU3RyaW5nQnVpbGRlciBzdHJpbmdCdWlsZGVyID0gbmV3IFN0cmluZ0J1aWxkZXIoKTsKICAgICAgICBmb3IoaW50IHQgPSAxOyB0IDw9IG47IHQrKykgewogICAgICAgICAgICBidWZmZXJlZFJlYWRlci5yZWFkTGluZSgpOwogICAgICAgICAgICBhcnJbMF0gPSBidWZmZXJlZFJlYWRlci5yZWFkTGluZSgpLnRyaW0oKS50b0NoYXJBcnJheSgpOwogICAgICAgICAgICBhcnJbMV0gPSBidWZmZXJlZFJlYWRlci5yZWFkTGluZSgpLnRyaW0oKS50b0NoYXJBcnJheSgpOwogICAgICAgICAgICBhcnJbMl0gPSBidWZmZXJlZFJlYWRlci5yZWFkTGluZSgpLnRyaW0oKS50b0NoYXJBcnJheSgpOwogICAgICAgICAgICB2YWx1ZSA9IDA7CiAgICAgICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCAzOyBpKyspIHsKICAgICAgICAgICAgICAgIGZvcihpbnQgaiA9IDA7IGogPCAzOyBqKyspIHsKICAgICAgICAgICAgICAgICAgICBpZihhcnJbaV1bal0gPT0gJyMnKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIHZhbHVlICs9IChsb25nKShNYXRoLmFicyhpIC0gMikgKyBNYXRoLmFicyhqIC0gMikpIDw8IDUwOwogICAgICAgICAgICAgICAgICAgICAgICB2YWx1ZSArPSAoKGxvbmcpKGkgKiAzICsgaikgPDwgMzYpOwogICAgICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgICAgIHZhbHVlICs9IChsb25nKShNYXRoLmFicyhpIC0gY29vcmRbYXJyW2ldW2pdIC0gJzEnXVswXSkgKyBNYXRoLmFicyhqIC0gY29vcmRbYXJyW2ldW2pdIC0gJzEnXVsxXSkpIDw8IDUwOwogICAgICAgICAgICAgICAgICAgICAgICB2YWx1ZSB8PSAobG9uZykoKGFycltpXVtqXSAtICcwJykpIDw8ICgoaSAqIDMgKyBqKSAqIDQpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICB0bXAuY2xlYXIoKTsKICAgICAgICAgICAgaW0gPSB0cnVlOwogICAgICAgICAgICBjaGVjayA9IHZhbHVlICYgYm9hcmQ7CiAgICAgICAgICAgIGlmKCFpbXBvc3NpYmxlLmNvbnRhaW5zKGNoZWNrKSkgewogICAgICAgICAgICAgICAgcHJpb3JpdHlRdWV1ZS5jbGVhcigpOwogICAgICAgICAgICAgICAgcHJpb3JpdHlRdWV1ZS5vZmZlcih2YWx1ZSk7CiAgICAgICAgICAgICAgICBzZXQuY2xlYXIoKTsKICAgICAgICAgICAgICAgIHNldC5hZGQoY2hlY2spOwogICAgICAgICAgICAgICAgdG1wLmFkZChjaGVjayk7CiAgICAgICAgICAgICAgICBpbSA9IGZhbHNlOwogICAgICAgICAgICAgICAgd2hpbGUgKCFwcmlvcml0eVF1ZXVlLmlzRW1wdHkoKSkgewogICAgICAgICAgICAgICAgICAgIGN1ciA9IHByaW9yaXR5UXVldWUucG9sbCgpOwogICAgICAgICAgICAgICAgICAgIGlmICgoY3VyICYgYm9hcmQpID09IGFuc3dlcikgewogICAgICAgICAgICAgICAgICAgICAgICBzdHJpbmdCdWlsZGVyLmFwcGVuZChjdXIgPj4gNTEpLmFwcGVuZCgnXG4nKTsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGludCBpID0gKGludCkgKChjdXIgPj4gMzYpICYgMTVMKTsKICAgICAgICAgICAgICAgICAgICByID0gY29vcmRbaV1bMF07CiAgICAgICAgICAgICAgICAgICAgYyA9IGNvb3JkW2ldWzFdOwogICAgICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgNDsgaisrKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIHZhbHVlID0gY3VyIC0gKChsb25nKSAoTWF0aC5hYnMociAtIDIpICsgTWF0aC5hYnMoYyAtIDIpKSA8PCA1MCk7CiAgICAgICAgICAgICAgICAgICAgICAgIG5yID0gciArIGRbal1bMF07CiAgICAgICAgICAgICAgICAgICAgICAgIG5jID0gYyArIGRbal1bMV07CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChuciA+PSAwICYmIG5yIDwgMyAmJiBuYyA+PSAwICYmIG5jIDwgMykgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgaW5kZXggPSBuciAqIDMgKyBuYzsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG51bSA9IChpbnQpICgoY3VyID4+IChpbmRleCAqIDQpKSAmIDE1KSAtIDE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB2YWx1ZSAmPSAofigxNUwgPDwgKGluZGV4ICogNCkpKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZhbHVlIHw9ICgobG9uZykgKG51bSArIDEpIDw8IChpICogNCkpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hlY2sgPSB2YWx1ZSAmIGJvYXJkOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYoaW1wb3NzaWJsZS5jb250YWlucyhjaGVjaykpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbSA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAoc2V0LmNvbnRhaW5zKGNoZWNrKSkgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICAgICAgdmFsdWUgKz0gKChsb25nKSAoTWF0aC5hYnMobnIgLSAyKSArIE1hdGguYWJzKG5jIC0gMikpIDw8IDUwKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZhbHVlIC09ICgobG9uZykgKE1hdGguYWJzKGNvb3JkW251bV1bMF0gLSBucikgKyBNYXRoLmFicyhjb29yZFtudW1dWzFdIC0gbmMpKSA8PCA1MCk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB2YWx1ZSArPSAoKGxvbmcpIChNYXRoLmFicyhjb29yZFtudW1dWzBdIC0gcikgKyBNYXRoLmFicyhjb29yZFtudW1dWzFdIC0gYykpIDw8IDUwKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZhbHVlICs9IG9uZUNvdW50OwogICAgICAgICAgICAgICAgICAgICAgICAgICAgdmFsdWUgPSAoKHZhbHVlICYgfigxNUwgPDwgMzYpKSB8ICgoKGxvbmcpIChuciAqIDMgKyBuYykpIDw8IDM2KSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBzZXQuYWRkKGNoZWNrKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRtcC5hZGQoY2hlY2spOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpb3JpdHlRdWV1ZS5vZmZlcih2YWx1ZSk7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgaWYoaW0pIHsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKGltIHx8IChjdXIgJiBib2FyZCkgIT0gYW5zd2VyKSB7CiAgICAgICAgICAgICAgICBpbXBvc3NpYmxlLmFkZEFsbCh0bXApOwogICAgICAgICAgICAgICAgc3RyaW5nQnVpbGRlci5hcHBlbmQoImltcG9zc2libGVcbiIpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIFN5c3RlbS5vdXQucHJpbnQoc3RyaW5nQnVpbGRlcik7CiAgICB9Cn0K
MTAwCgo4NjcKMjU0CjMjMQoKNjQ3Cjg1IwozMjEKCjg3Ngo1NDMKMjEjCgo4NyMKNTQ2CjMyMQoKODcjCjU0NgoyMTMKCjg3Iwo0NTYKMTIzCgo4NyMKNDI2CjM1MQoKODcjCjI1NgozNDEKCjg2Nwo1NDIKMzEjCgo4NjcKNTIxCjM0IwoKODY3CjUxNAozMiMKCjg2Nwo1IzQKMzEyCgo4NjcKNSMxCjMyNAoKODY3CjQjNQozMjEKCjg2NwoyNTQKMzEjCgo4NjcKMjU0CiMzMQoKODY3CjI0MQozNSMKCjg2NwoyIzQKMzUxCgo4NjcKMSM0CjMyNQoKODY1CjI3MQozNCMKCjg2NAo3IzUKMTIzCgo4NjMKNTcxCiMyNAoKODYxCjI3NAozNSMKCjg2Iwo3NTQKMTIzCgo4NiMKNDc1CjEyMwoKODYjCjI3NQozNDEKCjg1NwoyNjEKMzQjCgo4NTcKMTQ2CiMyMwoKODUzCjc2MgojNDEKCjg1MQoyIzQKMzY3Cgo4NSMKNDY3CjEyMwoKODQ3CjY1MgozMSMKCjg0NwoyNjUKMzEjCgo4NDcKMTU2CjMyIwoKODMyCjU0Nwo2MSMKCjgzMQo1NjQKIzI3Cgo4MjEKMzY0CiM1NwoKODIjCjU3MQozNjQKCjc4Ngo1NDMKMTIjCgo3ODYKNDM1CjEyIwoKNzg2CjQyNQojMzEKCjc4NgoxNTQKMjMjCgo3ODYKMTU0CiMyMwoKNzg1CjQ2MwoxMiMKCjc4NQo0IzYKMTIzCgo3ODUKMjYxCjM0IwoKNzgjCjY1Mwo0MjEKCjc4Iwo0NTYKMzIxCgo3OCMKNDM2CjEyNQoKNzgjCjE1NAozMjYKCjY4NwoyNTEKMzQjCgo2NyMKNDg1CjEyMwoKNjU4CjcyMQo0MyMKCjY1Nwo4NDIKMzEjCgo2NTcKODIxCjM0IwoKNjU3CjgxNAozMiMKCjY1Nwo4IzQKMzEyCgo2NTcKOCMxCjMyNAoKNjU3CjQzOAojMTIKCjY1NwozMjQKIzgxCgo2NTQKMzIxCjg3IwoKNjU0CjMyMQojODcKCjY1Iwo4MzQKNzEyCgo2NSMKNzg0CjEyMwoKNjQ3Cjg1MQozMiMKCjY0Nwo4MzUKMTIjCgo2NDcKODMyCjUxIwoKNjQ3CjgzMgojNTEKCjY0Nwo4MjUKMzEjCgo2NDcKOCM1CjMyMQoKNjQ3CjU4MgozMSMKCjY0Nwo1IzgKMTIzCgo2NDcKMzUyCiM4MQoKNjQ3CjI4MQozNSMKCjY0Iwo4NTcKMzIxCgo2MzEKODU0CiMyNwoKNjMxCjgjNAoyNTcKCjYzIwo1ODIKNzQxCgo2MjcKOCM0CjM1MQoKNjI3CjM0NQojODEKCjYyMQo4MzQKIzU3Cgo2MjEKNTg0CiMzNwoKNjIxCjM1NAojODcKCjYxNwo4IzQKMzI1Cgo2MTcKMjU0CjM4IwoKNjEjCjUyNAozODcKCjU4Nwo2NDIKMzEjCgo1ODcKNjIxCjM0IwoKNTg3CjIjNAozNjEKCjU4Iwo0NzYKMTIzCgo1NzgKNCM2CjEyMwoKNTc4CjMyNgojNDEKCjU3Iwo0NjgKMTIzCgo1NyMKMzQyCjY4MQoKNTcjCjI2OAozNDEKCjU2Mwo4IzIKNzQxCgo1NDcKNiM4CjMyMQoKNTQ3CjM4MgojNjEKCjU0NwoyMTgKMzYjCgo1MjEKNjM0CiM4NwoK
100
867
254
3#1
647
85#
321
876
543
21#
87#
546
321
87#
546
213
87#
456
123
87#
426
351
87#
256
341
867
542
31#
867
521
34#
867
514
32#
867
5#4
312
867
5#1
324
867
4#5
321
867
254
31#
867
254
#31
867
241
35#
867
2#4
351
867
1#4
325
865
271
34#
864
7#5
123
863
571
#24
861
274
35#
86#
754
123
86#
475
123
86#
275
341
857
261
34#
857
146
#23
853
762
#41
851
2#4
367
85#
467
123
847
652
31#
847
265
31#
847
156
32#
832
547
61#
831
564
#27
821
364
#57
82#
571
364
786
543
12#
786
435
12#
786
425
#31
786
154
23#
786
154
#23
785
463
12#
785
4#6
123
785
261
34#
78#
653
421
78#
456
321
78#
436
125
78#
154
326
687
251
34#
67#
485
123
658
721
43#
657
842
31#
657
821
34#
657
814
32#
657
8#4
312
657
8#1
324
657
438
#12
657
324
#81
654
321
87#
654
321
#87
65#
834
712
65#
784
123
647
851
32#
647
835
12#
647
832
51#
647
832
#51
647
825
31#
647
8#5
321
647
582
31#
647
5#8
123
647
352
#81
647
281
35#
64#
857
321
631
854
#27
631
8#4
257
63#
582
741
627
8#4
351
627
345
#81
621
834
#57
621
584
#37
621
354
#87
617
8#4
325
617
254
38#
61#
524
387
587
642
31#
587
621
34#
587
2#4
361
58#
476
123
578
4#6
123
578
326
#41
57#
468
123
57#
342
681
57#
268
341
563
8#2
741
547
6#8
321
547
382
#61
547
218
36#
521
634
#87