탈출

전설의 구슬은 3개 층으로 이루어진 던전의 맨 아래층에 놓여 있다. 주인공은 함정과 괴물을 모두 뚫고 내려가 구슬을 손에 넣었다. 구슬을 들어 올리는 순간 던전이 흔들리기 시작한다. 판데모니움의 군주들이 도둑질을 알아챈 것이다. 오래 머무르면 붙잡히므로, 구슬을 들고 최대한 빨리 밖으로 나가야 한다.

던전은 3개 층이다. 맨 위가 1층, 맨 아래가 3층이고, 구슬이 있는 방은 3층에 있다. 각 층은 $50 \times 50$ 격자다. 왼쪽 아래 칸의 좌표는 $(0, 0)$이고 두 좌표 모두 $0$부터 $49$까지다. 각 칸은 벽 칸이거나 바닥 칸이다. 벽 칸에는 들어갈 수 없고 바닥 칸은 자유롭게 지나간다.

바닥 칸에는 한 층 위로 올라가는 사다리가 있거나, 한 층 아래의 사다리와 이어진 뚜껑문이 있을 수 있다. 이웃한 바닥 칸으로 옮겨 가는 데 1의 시간이 들고, 사다리를 타고 올라가는 데도 1의 시간이 든다. 상하좌우뿐 아니라 대각선으로도 움직일 수 있고, 들어가는 칸이 벽이 아니기만 하면 된다. 뚜껑문은 아래쪽에서 잠겨 있어 아래층으로 내려가지 못한다. 사다리를 한 번 오르면 뚜껑문이 등 뒤에서 잠기므로 올라온 층으로 되돌아갈 수 없다.

3층에는 위로 가는 사다리가 3개 있고 뚜껑문은 없다. 1층에는 뚜껑문이 3개 있고 던전 밖으로 나가는 출구 사다리가 하나 있다. 2층에는 아래로 이어진 뚜껑문 3개와 위로 가는 사다리 3개가 있다. 출구 사다리를 뺀 사다리와 뚜껑문에는 0, 1, 2번이 붙어 있고, 어떤 층의 $i$번 사다리는 한 층 위의 $i$번 뚜껑문이 있는 칸으로 이어진다. 같은 층에서 이 사다리와 뚜껑문은 서로 다른 칸에 있다.

1층 출구 사다리가 있는 칸까지 가는 데 걸리는 가장 짧은 시간을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 5$)

각 테스트 케이스는 3개의 줄로 이루어지고, 3층, 2층, 1층 순서로 주어진다.

첫째 줄에는 3층의 정보가 주어진다. 먼저 주인공이 서 있는 칸의 좌표가 두 정수로 주어지고, 이어서 0번, 1번, 2번 사다리의 좌표가 차례로 주어진다. 그다음 이 층의 벽 칸 개수 $W$가 주어지고, 벽 칸 $W$개의 좌표가 이어진다.

둘째 줄에는 2층의 정보가 주어진다. 0번, 1번, 2번 뚜껑문의 좌표, 0번, 1번, 2번 사다리의 좌표, 벽 칸 개수 $W$, 벽 칸 $W$개의 좌표가 차례로 주어진다.

셋째 줄에는 1층의 정보가 주어진다. 0번, 1번, 2번 뚜껑문의 좌표, 출구 사다리의 좌표, 벽 칸 개수 $W$, 벽 칸 $W$개의 좌표가 차례로 주어진다.

좌표는 x y 순서로 주어지고 $0 \le x, y \le 49$다. 한 층의 벽 칸 좌표는 모두 다르며, 시작 칸이나 사다리, 뚜껑문이 있는 칸과 겹치지 않는다. $0 \le W \le 2500$이다. 탈출 경로는 항상 존재한다.

각 테스트 케이스마다 1층 출구 사다리가 있는 칸에 도착하는 데 걸리는 최소 시간을 한 줄에 하나씩 출력한다. 출구 사다리를 타고 올라가는 시간은 세지 않는다.

예제에서는 3층에서 0번 사다리를 타고, 2층에서 2번 사다리를 타는 경로가 가장 짧다. 칸 사이를 8번 이동하고 사다리를 2번 오르므로 답은 10이다.