#1960 주승규의 신문배달 Hard

13  20 s   128 MB  

Description

승규는 평소 주변 사람들을 위해 돈을 쓰는 것을 극도로 아끼는 구두쇠지만 여자친구에게 쓰는 돈이라면 이야기가 달라진다.

다가오는 여자친구와의 100일을 위한 자금을 마련하기 위한 승규는 어느날 신문배달을 시작했다.
그러나 게으름의 극치를 달리고 있는 승규는 며칠 지나지 않아 금방 지쳐버리고 말았다. 하지만 그녀와의 100일 위해서라면 비록 고x가 되더라도 어떻게든 돈을 모아야 하는법.
궁리 끝에 승규는 신문배달의 루트를 최소화하여 초딩만도 못한 체력의 한계를 어떻게든 보완하고자 하였지만 최단 루트를 찾아내는 것 역시 쉬운일이 아니었다.
 
신문소의 좌표와 배달을 해야 할 집의 좌표가 주어졌을 때 모든 집에 신문을 배달하기 위한 최단 경로를 구하는 프로그램을 작성하라.
출발은 신문소에서 시작하며 이동은 X축 또는 Y축에 평행하게만 움직일 수 있다. 모든 집을 한 번씩 다 돈 순간 배달이 종료된다고 가정한다.

Input

맨 처음 테스트 케이스의 수 T가 주어진다. T는 1 이상 10 이하이다.

그 다음 배달을 해야 할 집의 수 N과 신문소의 좌표 SX, SY가 주어진다.
그 다음 N만큼 배달을 해야 할 집의 좌표 Xi, Yi가 주어진다.
N은 1 이상 20 이하이며 각 좌표의 값은 0 이상 1000 이하이다.

Output

각 테스트 케이스마다 승규가 배달해야할 루트의 최소 거리를 출력한다.

Sample Input

Sample Output

2
2 0 0
0 1
1 0
3 0 1
1 2
2 10
3 5
3
13