경로 찾기

TooDee는 $2$차원 직교좌표 평면 위의 지역으로, 이곳에는 벌처럼 생긴 영리한 $2$차원 생물 Dee들이 산다. TooDee에는 벌집이 있는데, 각 벌집은 모든 변이 좌표축과 평행한 직사각형 모양이다.

Dee는 정해진 규칙에 따라서만 날 수 있다. 비행 경로는 좌표축과 평행한(수평 또는 수직) 선분들로 이루어지며, 모든 선분의 양 끝점 좌표는 정수이다. TooDee에서 다루는 모든 점의 좌표는 정수이고, Dee의 비행 규칙은 다음과 같다.

• 현재 위치가 점 $(x, y)$이면, 인접한 네 점 $(x+1, y)$, $(x-1, y)$, $(x, y+1)$, $(x, y-1)$ 중 하나로 이동할 수 있다.
• 벌집의 내부로는 들어갈 수 없다(벌집의 변이나 꼭짓점 위에 있는 것은 허용된다).
• 벌집의 변이나 꼭짓점 위에 있을 때에만 비행 방향을 바꿀 수 있다.
• 출발할 때에는 상하좌우 네 방향 중 하나를 자유롭게 선택할 수 있다.

오늘 밤은 TooDee의 복지 담당관 Deeficer의 딸 생일이라, Deeficer는 사무실에서 집으로 최대한 빨리 돌아가려 한다. Dee는 $1$초에 길이 $1$만큼 이동한다. 위 규칙을 지키면서 사무실에서 집까지 도착하는 데 걸리는 최소 시간(초)을 구하라.

첫 줄에 테스트 시나리오의 수 $T$ ($1 \le T \le 20$)가 주어진다. 이어서 $T$개의 시나리오가 주어지며, 각 시나리오 앞에는 빈 줄이 하나 있다.

각 시나리오의 첫 줄에는 네 정수가 주어진다. 앞의 두 정수는 사무실의 $x$, $y$ 좌표이고, 뒤의 두 정수는 집의 $x$, $y$ 좌표이다. 둘째 줄에는 벌집의 수 $N$이 주어진다. 이어지는 $N$개의 줄에는 각 벌집이 한 줄에 하나씩 주어지며, 벌집 직사각형의 대각으로 마주 보는 두 꼭짓점의 좌표(네 정수)로 표현된다.

서로 다른 두 벌집은 겹치지 않고, 변이 맞닿지도 않으며, 꼭짓점이 서로 닿지도 않는다. 사무실과 집의 위치는 서로 다르고, 각 벌집의 넓이는 $1$ 이상이다.

모든 좌표 값은 $-10^9$ 이상 $10^9$ 이하이며, $0 \le N \le 1000$이다.

각 시나리오마다 사무실에서 집까지 가장 빨리 가는 데 걸리는 시간(초)을 한 줄에 출력한다. 비행 규칙을 지키면서 집에 도달할 수 없으면 No Path를 출력한다.