Gold mining

mail@pastecode.io avatar
unknown
plain_text
a year ago
24 kB
0
Indexable
Never
*** De ***
Gold Mining
Given a map of gold mine which can be represented as a NxN matrix

In this map, there are several gold mines that locates on random places (maximum 4 mines each map). A camp will be setup in the map for mining the gold. Every day, workers will go from the camp to gold mines location. In order to reduce the cost, company want to setup the camp so that the distance from it to mining location is optimized.

Let consider below 5x5 map :



 - Worker can not go through the rock

 - It takes 1 hour to travel a cell in map

There are two mines, from start point (camp location), it would take 4h to go to each gold mine. Let's suppose the final cost will be the highest cost among them, then if we put the camp as above figure, the final cost will be 4.

Now, we consider other example :



In the 3rd example, the final cost will be minimum (1)

[Input]

The first line of input will be the number of test case T (T ≤ 50)

In each TC :

 - The first line will give the size of map N (N ≤ 20) and the number of gold mines G (2 ≤ G ≤ 4)

 - The next G lines will give location R (row) & C (column) of gold mine (1-base indexed)

- The next N lines will give the map's data : 1 represents the road & gold mines, 0 represents the rock (can not go through)

 

[Output]

Your program should output the Minimum final cost for traveling from camp to gold mines.

Case #1

1

Case #2

2

Case #3

2

Case #4

7

Case #5

6

 

[Constraints]

- You can move on 4 directions (up/left/down/right)

- You can not setup the camp on gold mine location or rock

- You can go pass a gold mine then go to other gold mine

- You must place camp so that workers can go to all gold mines


*** input ***

50
5 2
4 3
3 4
1 1 0 0 0
1 1 0 0 0
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1
8 2
5 6
6 4
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 0
1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
10 3
8 2
5 3
7 1
0 0 0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 0
1 0 0 1 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
8 3
1 2
2 8
5 8
0 1 0 0 0 0 0 0
0 1 0 1 1 1 1 1
0 1 0 1 0 0 0 1
0 1 1 1 0 0 0 1
0 1 0 1 0 0 0 1
0 1 0 1 1 1 1 1
0 1 0 0 1 0 0 0
0 1 0 0 1 0 0 0
10 4
9 6
1 9
7 5
7 3
1 1 1 1 1 1 0 1 1 0
1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1
1 0 1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1
1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 1 0 1
10 4
10 4
6 7
4 5
4 9
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1
1 1 0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0
0 0 1 1 1 0 1 0 1 1
10 3
10 5
6 9
7 8
1 0 0 1 1 0 0 0 0 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 0 0
10 3
5 2
4 6
6 5
1 0 1 1 1 1 1 0 1 1
1 1 0 1 1 0 1 1 1 1
1 0 0 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 0 1
0 0 1 1 0 1 1 1 1 1
0 1 0 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
10 3
9 5
1 3
7 4
0 1 1 1 1 0 1 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 0 0 1 1 1
1 0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1
0 0 0 1 0 1 1 0 1 1
0 0 0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1 1 1
10 3
1 10
6 2
4 6
0 1 1 1 1 1 0 1 0 1
1 1 1 1 0 1 1 1 0 1
0 0 1 1 0 0 1 0 1 1
0 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 0 0
10 2
4 4
4 5
0 1 1 1 1 1 1 1 1 1
0 1 0 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1
10 4
7 4
9 4
4 6
4 8
1 1 1 0 0 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 0 1 1
0 0 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
0 1 1 1 0 1 0 1 1 1
1 1 1 0 1 1 1 0 0 1
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 0
10 4
1 3
6 6
2 5
8 5
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
0 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1
10 2
3 2
6 7
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 0
0 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1
1 1 0 0 0 0 1 1 1 1
10 4
7 5
1 7
2 4
9 10
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
10 2
4 5
2 2
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 0 1
1 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1
10 2
8 5
10 7
1 1 1 1 1 0 1 1 1 1
1 0 1 0 1 1 1 1 1 1
1 0 1 0 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1
10 2
2 4
10 5
0 0 1 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 1 1 1 1 1 0 0 1 0
1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 0
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0 1 1
1 1 0 1 1 1 1 1 1 1
10 2
7 8
3 8
1 1 1 1 1 1 0 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1
0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 0 1 1 1
10 4
9 9
9 2
10 7
1 2
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
12 3
4 3
6 6
6 11
0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 0
0 1 0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 1 1
1 1 0 1 0 1 1 0 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0
0 1 1 1 0 1 1 1 1 1 0 1
1 1 1 0 1 0 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1
12 3
10 2
4 9
4 10
1 0 1 0 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 0 1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 1
1 0 1 1 1 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1 1 1 1 0
12 4
12 12
2 8
8 5
7 4
1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0
0 1 1 1 1 1 1 1 1 0 1 1
1 1 0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 0 0 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 0 1 1
12 4
11 3
10 5
6 12
12 7
1 0 0 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 0 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
12 4
11 2
2 10
5 11
5 12
1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1
12 2
9 8
7 9
1 1 1 1 1 1 1 1 1 0 0 0
1 0 1 1 1 1 0 0 1 1 0 0
1 1 1 1 1 0 0 1 1 0 0 1
1 1 1 1 1 0 1 0 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 0 1 1 1 1 1
1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1 1 0
12 2
7 9
10 8
1 0 1 1 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1
12 2
6 5
1 2
1 1 1 0 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0
1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 0 1 1 0
1 1 1 0 1 1 0 1 1 1 1 1
1 0 1 1 0 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0 1 1 1 1
1 0 1 1 1 1 1 1 1 1 0 1
12 4
7 6
7 12
5 5
5 4
0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 1 0 1 1
0 0 0 1 1 1 1 1 1 1 0 1
0 1 0 1 0 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
12 4
12 4
6 7
3 8
11 9
1 1 1 0 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 0 1 1
1 1 0 1 1 0 1 1 1 1 1 1
1 1 0 1 0 1 1 0 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1 0 1
1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1 1 0
15 3
8 6
8 5
12 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 0 1 1 1 1 1 1
1 1 0 1 1 1 1 0 0 0 1 1 1 0 1
1 1 1 1 1 0 1 1 0 1 1 1 1 1 1
1 1 0 1 0 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 0 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 0 1 1 1 1 1
0 1 0 1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 0 1 0 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 3
7 2
12 7
4 8
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 0 1 1 0 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 0 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
15 2
6 4
7 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 0 1 1 0 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0 1 1 1 1 0
1 1 1 1 1 1 1 0 0 1 1 1 1 1 1
1 1 1 1 0 1 1 0 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 2
4 2
3 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 0 1 0 1 0 1 1 1
1 1 1 1 1 1 1 1 0 0 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 0 1 1 1 0 1 1
0 1 1 1 1 0 0 1 0 1 1 1 1 1 1
15 4
1 8
10 6
9 7
9 8
1 1 1 0 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 0 1 1 0 1 0
1 1 1 1 1 0 0 1 1 1 0 0 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1
1 0 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 0 0 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 1 1 1 1 1 1 1 1
15 3
2 12
12 14
12 5
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1 0 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 0 1 0 0 1 1 1 1
1 0 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1 1 1 1 0 1
1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 3
9 6
11 4
1 3
1 0 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 0 1 0 1 0 1 0
1 1 1 0 1 0 1 1 0 1 1 0 1 1 0
1 0 1 0 0 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 0 1 0 0 1 0
0 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 0
15 3
15 7
1 4
2 7
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 0 0 1
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 0 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 0 0 1 0 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 0
1 1 1 1 1 1 1 1 0 0 1 1 1 1 0
1 0 1 1 1 1 1 0 0 0 0 1 1 1 0
15 4
8 8
1 5
1 12
6 12
1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 0 1 1 1 1 1 1 1 1 1 0 0
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 0 0 0 0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 0 1 0 1 1 1 1 1 1 1 0 1 0
0 1 1 1 1 0 1 0 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 3
3 11
15 12
1 7
0 1 1 1 1 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0
1 0 0 1 0 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 0 1 1 0 1 1
1 1 0 1 1 1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 1 1 1 0 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 0
20 2
6 12
12 11
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1
1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1
1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0
1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1
1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1
20 4
8 20
17 17
2 18
2 13
1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1
1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1
20 2
18 6
5 17
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0
1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0
0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1
0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0
20 3
8 11
11 14
13 16
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1
1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1
0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0
20 2
7 10
13 19
1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1
0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1
0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1
1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1
1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1
1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
20 3
6 2
10 7
14 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0
1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
20 3
9 8
8 12
7 12
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0
1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1
0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1
0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1
20 3
7 12
9 8
14 5
1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1
1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0
1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1
1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1
1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1
20 3
17 4
19 15
17 18
1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1
1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1
0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1
20 3
4 20
5 19
20 16
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1
1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0
1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1
1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1
0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1
1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 0

*** output ***
Case #1
1
Case #2
2
Case #3
2
Case #4
7
Case #5
6
Case #6
6
Case #7
4
Case #8
3
Case #9
6
Case #10
7
Case #11
2
Case #12
6
Case #13
5
Case #14
4
Case #15
7
Case #16
3
Case #17
2
Case #18
5
Case #19
3
Case #20
8
Case #21
5
Case #22
7
Case #23
7
Case #24
7
Case #25
9
Case #26
2
Case #27
2
Case #28
4
Case #29
5
Case #30
7
Case #31
3
Case #32
6
Case #33
1
Case #34
2
Case #35
6
Case #36
9
Case #37
6
Case #38
10
Case #39
6
Case #40
10
Case #41
4
Case #42
10
Case #43
12
Case #44
5
Case #45
10
Case #46
6
Case #47
3
Case #48
7
Case #49
8
Case #50
11


*** my code ***
#include<iostream>
using namespace std;
int ans;
int N, G;
int goldXY[25][2];
int map[25][25];
 
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int visit[25][25];

void resetmap(){
	for (int i = 0; i < 25; i++){
		for ( int j = 0; j < 25; j++){
			map[i][j] = -1;
		}
	}
	golds = 0;
}

void resetvisit(){
	for (int i = 0; i < 25; i++){
		for ( int j = 0; j < 25; j++){
			visit[i][j] = 1000000;
		}
	}
}

// queue
int qx[100000];
int qy[100000];
int front = -1;
int rear = -1;
bool isEmpty(){
	return front == -1;
}
void push(int x, int y){
	if (front == -1) front = 0;
	rear++;
	qx[rear] = x;
	qy[rear] = y;
}
void pop(){
	if (front >= rear) front = rear = -1;
	else front++;
}

int BFS(int x, int y){
	front = rear = -1;
	push(x,y);
	visit[x][y] = 0;
	int cnt = 0;
	int len = 0;
	while (!isEmpty()){
		int x1 = qx[front];
		int y1 = qy[front];
		pop();
		for (int i = 0; i < 4; i++){
			int x2 = x1 + dx[i];
			int y2 = y1 + dy[i];
			if (map[x2][y2] > 0 && x2>=0 && x2<N && y2>=0 && y2<N && visit[x2][y2] == 1000000){
				visit[x2][y2] = visit[x1][y1] + 1;
				push(x2,y2);
				if (map[x2][y2] == 2) {
					++cnt;
					if(cnt == G) {	// tim du so vang
						len = visit[x2][y2];
						return len;
					}
				}
			}
		}
	}
	return 10000;
}

int main(){
	freopen("input.txt","r",stdin);
	int TC; cin >> TC;
	for (int tc = 1; tc <= TC; tc++){
		resetmap();
		cin >> N >> G;
		for (int i = 0; i < G; i++){
			int R, C; cin >> R >> C;
			goldXY[i][0] = R-1;
			goldXY[i][1] = C-1;
		}
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				cin >> map[i][j];
			}
		}
		// gan map [vang] = 2
		for (int i = 0; i < G; i++){
			map[goldXY[i][0]][goldXY[i][1]] = 2;
		}

		ans = 1000;
		// tim diem xuat phat theo tung vi tri tren map
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				resetvisit();
				if (map[i][j] == 0 || map[i][j] == 2 || visit[i][j] == 1) continue;
				int len = BFS(i,j);
				// chon ra diem xuat phat tot nhat
				if (ans > len) ans = len;
			}
		}

		cout << "Case #" << tc << endl;
		cout << ans << endl;
	}
	return 0;
}