The Escape

The legendary orb lies at the bottom of a dungeon with three floors. You fought past every trap and every monster, and the orb is now in your bag. The moment you lift it the dungeon starts to shake, because the lords of Pandemonium have noticed the theft. Stay too long and they catch you, so you have to carry the orb out as fast as you can.

The dungeon has three floors. Floor 1 is the top floor, floor 3 is the bottom floor, and the chamber with the orb is on floor 3. Each floor is a $50 \times 50$ grid. The bottom left square is $(0, 0)$ and both coordinates run from $0$ to $49$. Every square is either a wall square or a floor square. You cannot enter a wall square, and you walk freely over floor squares.

A floor square may hold a ladder that leads up to the floor above, or a trapdoor connected to a ladder on the floor below. Moving to a neighboring floor square costs 1 time unit, and climbing a ladder also costs 1 time unit. You move in the four straight directions and diagonally as well, as long as the square you move into is not a wall. Trapdoors are locked from below, so you cannot use one to go down. Once you climb a ladder, the trapdoor locks behind you, so you cannot return to the floor you came from.

Floor 3 has three ladders up and no trapdoors. Floor 1 has three trapdoors and one exit ladder that leads out of the dungeon. Floor 2 has three trapdoors down and three ladders up. Every trapdoor and every ladder except the exit ladder is labelled 0, 1 or 2, and ladder $i$ on a floor leads to the square with trapdoor $i$ on the floor above. On one floor, no two of these ladders and trapdoors share a square.

Find the shortest time you need to reach the square with the exit ladder on floor 1.

The first line contains the number of test cases $T$. ($1 \le T \le 5$)

Each test case is a block of three lines, given in the order floor 3, floor 2, floor 1.

The first line describes floor 3. It starts with the coordinate of the square where the hero stands, given as two integers, followed by the coordinates of ladders 0, 1 and 2 in that order. After that comes the number of wall squares $W$ on this floor, followed by the coordinates of the $W$ wall squares.

The second line describes floor 2. It contains the coordinates of trapdoors 0, 1 and 2, the coordinates of ladders 0, 1 and 2, the number of wall squares $W$, and the coordinates of the $W$ wall squares, in that order.

The third line describes floor 1. It contains the coordinates of trapdoors 0, 1 and 2, the coordinate of the exit ladder, the number of wall squares $W$, and the coordinates of the $W$ wall squares, in that order.

Every coordinate is given as x y with $0 \le x, y \le 49$. On one floor the wall coordinates are all different, and no wall square is the starting square, a ladder square or a trapdoor square. $0 \le W \le 2500$. An escape route always exists.

For each test case print the smallest number of time units needed to reach the square with the exit ladder on floor 1, one per line. Do not count the climb up the exit ladder.

In the example the shortest route climbs ladder 0 on floor 3 and ladder 2 on floor 2. It moves between squares 8 times and climbs a ladder twice, so the answer is 10.