시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB0000.000%

문제

장기는 바둑과 함께 오랜 전통을 갖는 보드게임의 일종이다. 장기에서는 여러 종류의 기물들을 이용하여 상대방의 궁을 제압하는 것이 목적이며, 이를 위해 여러 수 앞을 내다보며 자신의 기물을 운용하는 것이 기본 전략이 된다. 여러 기물 중에 馬는 특히 민첩하게 움직일 수 있어 여러 모로 중요하게 사용된다. 하지만 초보들에게 馬는 그 움직임이 특별해서 그것을 잘 운용하기가 쉽지가 않다. 馬를 잘 운용하기 위해서는 현재 馬의 위치에서 가고자 하는 지점까지 최단경로로 가는 방법을 찾는 것은 기본 중에 기본이다.

馬의 이동방식은 아래 그림과 같다. 기본적으로 “ 한번의 이동” 에 날 일(日)자를 가로지르게 된다. 이것은 체스에서 knight 와 비슷하지만 馬는 직선으로 한번 대각선으로 한번 움직이는 것으로 생각하여 중간 위치에 다른 기물이 있을 때는 그것을 넘어가지 못한다. 


<그림 1: 馬의 이동방식>
馬는 “한 번의 이동”에 한 칸 앞으로 전진 한 뒤 대각선으로 이동 하여 전체적으로 날 일(日)자를 가로지르게 된다.
붉게 칠해진 원들이 (다른 기물이 중간에 없을 때에) 馬가 한번에 이동할 수 있는 위치이다. 

장기판에 다른 기물들과 馬가 놓여 있을 때에, 현재 위치에서 목적지점까지 馬가 최소 몇 번 이동해야 하는지를 계산하는 프로그램을 작성하시오. 장기판은 무한히 넓다고 가정하며, 馬의 현재 좌표와 목적지 좌표, 그리고 다른 기물들의 좌표들이 주어진다. 馬가 이동하는 동안 다른 기물들은 움직이지 않는다고 가정하며, 이 무한 장기판 위에 궁(대각선으로 그어진 이동경로)은 없다고 가정한다. 또한, 馬가 완전히 막혀서 목적지까지 가지 못하는 경우도 없다고 가정한다. 

 

입력

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에는 馬의 현재 좌표가 주어지고, 둘째 줄에 馬가 도착해야 할 좌표가 주어진다. 셋째 줄에는 다른 기물들의 수 K(0 ≤ K ≤ 10000)가 주어지고, 넷째 줄부터는 K개의 줄에 걸쳐, 다른 기물들의 좌표(즉, 馬를 놓을 수 없는 좌표)가 주어진다. 모든 좌표는 2개의 -10000이상 10000이하의 정수로 주어지며, 공백문자로 분리되어 있다. 

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 馬의 최소 이동횟수를 한 줄에 하나씩 출력한다.

예제 입력 1

3
0 0
3 3
0
0 0
6 0
5
2 1
1 2
2 0
2 -1
1 -2
-5 -150
195 50
1
-200 -200

예제 출력 1

2
6
134