3
10 10 10
0 200 201
300 0 200
200 100 0
2
500 500
0 120
200 0
2
220 220
0 30
20 0
2
150 150
0 120
200 0
1
421
0
1
420
0
1
301
0
1
300
0
1
1
0
5
420 420 420 420 420
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
5
419 419 419 419 419
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
5
1 1 1 1 1
0 419 419 419 419
419 0 419 419 419
419 419 0 419 419
419 419 419 0 419
419 419 419 419 0
5
1 1 1 1 1
0 420 420 420 420
420 0 420 420 420
420 420 0 420 420
420 420 420 0 420
420 420 420 420 0
5
300 300 300 300 300
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
5
299 299 299 299 299
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
5
1 1 1 1 1
0 299 299 299 299
299 0 299 299 299
299 299 0 299 299
299 299 299 0 299
299 299 299 299 0
5
1 1 1 1 1
0 300 300 300 300
300 0 300 300 300
300 300 0 300 300
300 300 300 0 300
300 300 300 300 0
5
20 20 20 20 20
0 40 40 40 40
40 0 40 40 40
40 40 0 40 40
40 40 40 0 40
40 40 40 40 0
5
30 30 30 30 30
0 80 80 80 80
80 0 80 80 80
80 80 0 80 80
80 80 80 0 80
80 80 80 80 0
8
25 28 20 16 19 26 28 27
0 34 40 21 34 37 27 25
32 0 29 23 29 28 31 30
26 27 0 37 25 31 20 35
27 20 25 0 25 40 27 26
27 39 33 33 0 35 28 28
33 20 24 27 25 0 33 27
38 31 28 28 34 28 0 33
20 29 25 23 31 30 31 0
8
32 20 29 11 15 40 18 22
0 27 58 45 23 46 53 36
40 0 32 28 49 20 53 41
24 24 0 43 46 31 60 24
46 36 23 0 31 38 52 46
25 41 46 34 0 52 31 20
21 47 42 40 43 0 57 21
50 48 46 49 57 46 0 35
42 28 42 20 26 33 52 0
8
96 29 23 28 44 59 23 99
0 73 57 69 54 42 50 71
44 0 64 60 65 46 93 68
91 99 0 60 69 82 66 58
84 94 96 0 78 62 99 78
44 45 85 43 0 40 64 71
67 69 75 81 65 0 62 100
55 87 66 61 43 82 0 82
95 67 81 47 64 52 42 0
10
11 29 29 13 27 20 21 34 25 37
0 40 23 28 34 38 30 39 26 30
30 0 34 24 32 24 27 40 38 37
20 23 0 25 36 37 32 35 36 21
21 38 20 0 24 20 20 37 26 23
23 33 40 30 0 38 30 32 34 36
35 40 35 39 24 0 31 32 37 30
36 28 32 37 36 33 0 20 23 30
25 21 38 39 26 28 37 0 21 33
22 26 37 21 20 28 30 38 0 35
34 23 40 28 32 28 20 29 23 0
12
24 22 24 30 21 25 27 25 22 20 27 26
0 36 35 36 33 31 37 36 38 31 40 38
40 0 39 37 38 35 38 32 38 34 38 35
38 30 0 30 40 35 39 40 37 36 32 31
39 39 38 0 37 34 33 31 34 36 40 40
34 31 38 38 0 30 34 37 30 40 40 37
30 30 33 30 33 0 30 40 39 30 39 32
32 37 40 31 30 34 0 30 36 39 32 31
33 40 31 40 33 35 33 0 40 40 36 32
40 31 36 31 39 40 38 33 0 32 38 33
34 30 31 30 30 30 34 36 38 0 31 34
37 30 34 34 40 30 34 34 38 33 0 32
33 35 40 38 33 36 37 38 34 34 38 0
15
25 35 33 35 30 38 22 33 22 35 27 34 34 33 24
0 30 39 53 49 46 34 51 44 51 53 37 53 38 60
33 0 57 31 37 46 48 42 33 37 38 53 58 48 31
54 39 0 40 46 37 58 35 42 38 46 47 49 46 42
49 42 54 0 54 39 41 49 34 51 41 48 34 50 40
44 42 44 51 0 39 50 31 39 53 31 49 30 44 57
30 46 32 56 51 0 53 50 30 31 49 60 57 51 52
37 53 38 33 44 40 0 35 43 57 43 43 51 46 34
58 43 54 42 55 42 36 0 36 59 48 31 42 37 32
35 31 49 35 48 48 51 45 0 38 57 40 44 49 45
59 59 58 58 48 45 51 36 38 0 31 35 30 50 34
54 51 60 42 58 44 40 33 57 54 0 40 44 40 30
31 41 36 46 35 36 50 52 39 56 37 0 40 52 31
58 32 44 52 31 55 60 44 33 32 33 53 0 42 58
43 32 43 53 55 31 35 45 33 57 58 39 43 0 47
38 46 36 39 43 48 46 38 37 33 54 33 52 37 0
20
51 57 44 50 69 44 58 58 62 54 45 45 41 67 41 51 65 42 67 46
0 61 64 42 43 62 62 61 66 48 45 57 46 51 58 49 62 57 59 65
64 0 63 61 42 43 43 54 61 41 63 68 57 54 62 67 67 59 63 61
59 68 0 56 45 60 52 58 56 50 42 44 68 66 55 60 49 50 60 46
61 43 48 0 49 63 64 44 46 60 56 66 51 68 64 49 66 53 57 68
48 52 49 51 0 43 45 59 58 64 40 67 66 63 46 51 45 54 62 40
49 57 43 67 52 0 56 40 51 46 45 57 55 44 51 62 60 50 61 44
56 50 67 51 47 67 0 47 57 43 43 45 69 59 48 51 58 42 56 66
50 43 48 40 51 52 45 0 50 69 64 57 48 43 65 61 42 60 41 66
54 50 46 61 58 49 58 44 0 41 64 63 59 58 48 40 48 47 57 48
53 58 53 57 61 40 57 53 44 0 69 66 45 61 60 69 59 66 68 43
54 68 64 69 59 42 55 65 43 43 0 53 67 44 63 48 40 58 58 40
66 48 51 69 48 59 47 52 52 68 62 0 48 69 50 57 48 51 55 68
56 61 42 64 42 55 58 66 62 66 45 63 0 59 52 64 46 51 58 42
61 41 69 57 46 62 69 45 42 60 60 43 59 0 51 58 61 49 55 53
62 65 42 65 68 56 67 67 62 42 69 64 51 69 0 66 49 68 52 45
65 54 59 41 42 65 40 68 43 69 43 59 56 47 59 0 59 47 46 59
53 45 67 56 66 65 48 62 45 64 64 41 66 41 66 63 0 63 65 55
53 52 48 42 45 63 46 41 68 46 62 41 44 46 42 59 41 0 55 60
53 66 54 69 52 49 43 54 64 60 45 49 56 43 44 42 48 48 0 47
45 58 51 42 65 57 44 54 64 64 54 52 69 53 60 57 47 58 57 0
20
71 97 64 30 99 54 108 88 92 94 35 75 111 57 91 121 125 72 57 66
0 8 5 7 8 9 9 8 7 7 10 10 5 10 5 8 9 10 6 6
5 0 10 8 7 8 8 7 8 6 10 9 10 7 9 8 8 6 10 8
6 9 0 9 10 7 5 5 9 9 7 9 9 7 8 7 8 9 7 5
8 8 7 0 8 10 5 9 5 7 9 7 10 9 5 8 7 6 10 9
7 5 8 10 0 8 10 6 5 5 5 8 7 10 5 10 10 7 9 5
8 10 8 8 5 0 9 5 10 5 10 10 8 9 10 9 7 9 8 9
9 9 8 10 6 8 0 6 10 8 8 10 10 6 7 10 5 7 9 7
9 8 7 5 10 5 10 0 9 10 5 10 7 8 6 8 7 7 6 7
7 9 5 8 5 8 5 9 0 6 5 10 6 5 7 5 7 6 10 7
6 5 6 10 8 5 10 6 9 0 10 7 10 8 7 10 6 7 9 8
7 9 5 10 6 7 8 6 8 8 0 6 8 9 10 7 5 5 5 5
7 7 10 10 7 6 6 5 5 9 9 0 7 10 9 10 7 10 8 9
9 8 7 5 7 8 5 7 9 7 10 10 0 6 5 5 5 10 5 7
8 6 10 10 5 9 10 10 7 7 7 8 6 0 10 5 8 8 8 6
9 6 7 6 9 9 8 8 9 7 10 5 10 10 0 7 8 9 5 10
6 7 6 6 7 6 5 9 8 10 8 6 9 6 6 0 6 6 5 6
6 10 8 9 7 6 7 9 10 5 5 6 7 6 7 10 0 10 6 8
6 5 7 7 10 10 5 6 9 5 9 6 9 5 7 6 6 0 8 7
6 7 7 10 5 8 8 7 5 7 10 8 9 8 9 7 7 7 0 6
10 5 10 7 6 10 9 7 5 5 7 5 10 6 7 10 6 5 10 0
20
71 117 64 30 129 54 128 88 112 104 35 75 121 37 91 121 125 72 47 66
0 8 5 7 8 9 9 8 7 7 10 10 5 10 5 8 9 10 6 6
5 0 10 8 7 8 8 7 8 6 10 9 10 7 9 8 8 6 10 8
6 9 0 9 10 7 5 5 9 9 7 9 9 7 8 7 8 9 7 5
8 8 7 0 8 10 5 9 5 7 9 7 10 9 5 8 7 6 10 9
7 5 8 10 0 8 10 6 5 5 5 8 7 10 5 10 10 7 9 5
8 10 8 8 5 0 9 5 10 5 10 10 8 9 10 9 7 9 8 9
9 9 8 10 6 8 0 6 10 8 8 10 10 6 7 10 5 7 9 7
9 8 7 5 10 5 10 0 9 10 5 10 7 8 6 8 7 7 6 7
7 9 5 8 5 8 5 9 0 6 5 10 6 5 7 5 7 6 10 7
6 5 6 10 8 5 10 6 9 0 10 7 10 8 7 10 6 7 9 8
7 9 5 10 6 7 8 6 8 8 0 6 8 9 10 7 5 5 5 5
7 7 10 10 7 6 6 5 5 9 9 0 7 10 9 10 7 10 8 9
9 8 7 5 7 8 5 7 9 7 10 10 0 6 5 5 5 10 5 7
8 6 10 10 5 9 10 10 7 7 7 8 6 0 10 5 8 8 8 6
9 6 7 6 9 9 8 8 9 7 10 5 10 10 0 7 8 9 5 10
6 7 6 6 7 6 5 9 8 10 8 6 9 6 6 0 6 6 5 6
6 10 8 9 7 6 7 9 10 5 5 6 7 6 7 10 0 10 6 8
6 5 7 7 10 10 5 6 9 5 9 6 9 5 7 6 6 0 8 7
6 7 7 10 5 8 8 7 5 7 10 8 9 8 9 7 7 7 0 6
10 5 10 7 6 10 9 7 5 5 7 5 10 6 7 10 6 5 10 0
20
41 117 64 30 129 54 128 88 112 104 35 75 121 37 124 121 125 72 39 66
0 8 5 7 8 9 9 8 7 7 10 10 5 10 5 8 9 10 6 6
5 0 10 8 7 8 8 7 8 6 10 9 10 7 9 8 8 6 10 8
6 9 0 9 10 7 5 5 9 9 7 9 9 7 8 7 8 9 7 5
8 8 7 0 8 10 5 9 5 7 9 7 10 9 5 8 7 6 10 9
7 5 8 10 0 8 10 6 5 5 5 8 7 10 5 10 10 7 9 5
8 10 8 8 5 0 9 5 10 5 10 10 8 9 10 9 7 9 8 9
9 9 8 10 6 8 0 6 10 8 8 10 10 6 7 10 5 7 9 7
9 8 7 5 10 5 10 0 9 10 5 10 7 8 6 8 7 7 6 7
7 9 5 8 5 8 5 9 0 6 5 10 6 5 7 5 7 6 10 7
6 5 6 10 8 5 10 6 9 0 10 7 10 8 7 10 6 7 9 8
7 9 5 10 6 7 8 6 8 8 0 6 8 9 10 7 5 5 5 5
7 7 10 10 7 6 6 5 5 9 9 0 7 10 9 10 7 10 8 9
9 8 7 5 7 8 5 7 9 7 10 10 0 6 5 5 5 10 5 7
8 6 10 10 5 9 10 10 7 7 7 8 6 0 10 5 8 8 8 6
9 6 7 6 9 9 8 8 9 7 10 5 10 10 0 7 8 9 5 10
6 7 6 6 7 6 5 9 8 10 8 6 9 6 6 0 6 6 5 6
6 10 8 9 7 6 7 9 10 5 5 6 7 6 7 10 0 10 6 8
6 5 7 7 10 10 5 6 9 5 9 6 9 5 7 6 6 0 8 7
6 7 7 10 5 8 8 7 5 7 10 8 9 8 9 7 7 7 0 6
10 5 10 7 6 10 9 7 5 5 7 5 10 6 7 10 6 5 10 0
20
10 10 9 9 10 9 5 5 9 7 10 10 6 8 6 10 6 7 8 5
0 8 5 7 8 9 9 8 7 7 10 10 5 10 5 8 9 10 6 6
5 0 10 8 7 8 8 7 8 6 10 9 10 7 9 8 8 6 10 8
6 9 0 9 10 7 5 5 9 9 7 9 9 7 8 7 8 9 7 5
8 8 7 0 8 10 5 9 5 7 9 7 10 9 5 8 7 6 10 9
7 5 8 10 0 8 10 6 5 5 5 8 7 10 5 10 10 7 9 5
8 10 8 8 5 0 9 5 10 5 10 10 8 9 10 9 7 9 8 9
9 9 8 10 6 8 0 6 10 8 8 10 10 6 7 10 5 7 9 7
9 8 7 5 10 5 10 0 9 10 5 10 7 8 6 8 7 7 6 7
7 9 5 8 5 8 5 9 0 6 5 10 6 5 7 5 7 6 10 7
6 5 6 10 8 5 10 6 9 0 10 7 10 8 7 10 6 7 9 8
7 9 5 10 6 7 8 6 8 8 0 6 8 9 10 7 5 5 5 5
7 7 10 10 7 6 6 5 5 9 9 0 7 10 9 10 7 10 8 9
9 8 7 5 7 8 5 7 9 7 10 10 0 6 5 5 5 10 5 7
8 6 10 10 5 9 10 10 7 7 7 8 6 0 10 5 8 8 8 6
9 6 7 6 9 9 8 8 9 7 10 5 10 10 0 7 8 9 5 10
6 7 6 6 7 6 5 9 8 10 8 6 9 6 6 0 6 6 5 6
6 10 8 9 7 6 7 9 10 5 5 6 7 6 7 10 0 10 6 8
6 5 7 7 10 10 5 6 9 5 9 6 9 5 7 6 6 0 8 7
6 7 7 10 5 8 8 7 5 7 10 8 9 8 9 7 7 7 0 6
10 5 10 7 6 10 9 7 5 5 7 5 10 6 7 10 6 5 10 0
12
10 10 10 10 10 10 10 10 10 10 10 350
0 10 10 10 10 10 10 10 10 10 10 10
10 0 10 10 10 10 10 10 10 10 10 10
10 10 0 10 10 10 10 10 10 10 10 10
10 10 10 0 10 10 10 10 10 10 10 10
10 10 10 10 0 10 10 10 10 10 10 10
10 10 10 10 10 0 10 10 10 10 10 10
10 10 10 10 10 10 0 10 10 10 10 10
10 10 10 10 10 10 10 0 10 10 10 10
10 10 10 10 10 10 10 10 0 10 10 10
10 10 10 10 10 10 10 10 10 0 10 10
10 10 10 10 10 10 10 10 10 10 0 10
10 10 10 10 10 10 10 10 10 10 10 0
0