시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

The legendary orb of Zot lies at the bottom of a 27 floor dungeon, guarded by deadly traps and horrible monsters. You, the brave hero, have fought your way to the bottom of this dungeon. You have killed every monster and destroyed every trap. Now you stand in the chamber with the orb. Many have died trying to reach this room, but you have succeeded. Not hesitating, you pick up the orb and put it in your bag. As you lift the orb from its resting place, it makes a horrible scream, and the dungeon begins to shake. The terrible lords of Pandemonium have noticed your crime. They gather their power to punish you. If you stay in the dungeon too long, they will reach inside your mind with their disgusting magic tentacles and squeeze your brain out through your ears. You must escape with the orb before this happens.

The dungeon has 27 floors. The chamber with the orb is on the bottom floor (floor 27th). Each floor is considered to be a 50 by 50 grid. The bottom left square is labelled (0,0). A square in the grid is either a wall square (in which case you cannot move through it), or a floor square. You can move freely through floor squares. In addition to this, a floor square may contain a ladder leading up to the next floor, or a trapdoor connected to a ladder on the lower floor. It costs 1 arbitrary time unit to move from one floor square to another, and it costs 1 arbitrary time unit to use ladders up. You can move in any of the four standard directions, and you can also move diagonally (provided there is no wall in the space you are moving into). Trapdoors are locked from the bottom, so you cannot use a trapdoor to go down to a lower floor. Once you have climbed a ladder the trapdoor it links to locks behind you and you may not return to the floor you came from.

On the 27th floor there are 3 ladders up, and no trapdoors down. On the top floor (floor 1) there are 3 trapdoors down, and one ladder up (the exit). On every floor in between there are 3 ladders up and 3 trapdoors down. Ladders (except the exit on floor 1) and trapdoors come in pairs, and are labelled 0, 1, or 2. So, for example, ladder number 1 leads up to the square containing trapdoor number 1 on the floor above. A ladder or trapdoor cannot be in the same square as another ladder or trapdoor. 

입력

The first line of input is a number indicating the number of test cases (at most 5 test cases). Each test case is a block of 27 lines. The format is as follows:

The first line of a test case begins with a pair of numbers representing the starting coordinate of the hero floor 27. Following this are 3 pairs of numbers. These represent the coordinates of the ladders 0, 1, and 2 on floor 27 respectively. Following this is a single number. This tells you how many wall squares are on this floor. After this come pairs of coordinates representing the positions of the wall squares.

Lines 2-26 of a test case have this format: The line begins with 3 pairs of numbers representing the coordinates of the 3 trapdoors down. Following this are 3 pairs of numbers representing the coordinates of the ladders up. Following this is a number representing the number of wall squares, and after this are pairs of numbers representing the coordinates of the wall squares.

Line 27 of a test case has this format: The line begins with 3 pairs of number representing the coordinates of the 3 trapdoors down. Following this is a pair representing the location of the ladder exiting the dungeon. Following this is a number representing the number of wall squares, and pairs of numbers representing the coordinates of the wall squares as usual.

출력

For each test case output a single number representing the smallest number of moves it takes the hero to get to the exit ladder (you should not include the move it takes to use the exit ladder). It is guaranteed that there is an escape route (after all, you have walked that route down to the 27th floor)

예제 입력

1
0 0 4 4 3 1 3 4 3 1 2 2 2 3 2
0 0 4 0 0 4 2 2 4 4 0 1 5 2 1 3 3 2 0 1 1 1 2
0 0 0 2 3 4 4 4 5 0 1 1 0 2 0 3 0 4 0

예제 출력

10

힌트

In this example the shortest path is obtained by using L0 then L2, for a total cost of 10 (8 squares and 2 ladders).