비퍼 수집하기

카렐(Karel)은 각 위치가 정수 좌표 $(x, y)$로 표현되는 직사각형 좌표계에 사는 로봇입니다. 이 세계 곳곳에는 비퍼(beeper)가 놓여 있고, 카렐은 이들을 모두 주워야 합니다. 카렐은 $x$축 또는 $y$축 방향으로만 이동할 수 있으며, 대각선으로는 이동할 수 없습니다. 인접한 위치로 한 칸 이동하면 거리 $1$이 소모되므로, 두 위치 사이의 이동 거리는 두 좌표의 맨해튼 거리(각 좌표 차이의 절댓값의 합)와 같습니다.

카렐은 시작 위치에서 출발하여 비퍼가 놓인 모든 위치를 방문한 뒤 다시 시작 위치로 돌아와야 합니다. 카렐이 이동하는 전체 경로의 최소 길이를 구하세요. 비퍼를 방문하는 순서는 자유롭게 정할 수 있습니다.

첫째 줄에 시나리오의 개수가 주어집니다. 각 시나리오는 다음과 같이 구성됩니다.

• 첫째 줄: 세계의 크기를 나타내는 두 정수 (가로 크기와 세로 크기)
• 둘째 줄: 카렐의 시작 위치를 나타내는 두 정수 $x$, $y$
• 셋째 줄: 비퍼의 개수 $n$
• 이어지는 $n$개의 줄: 각 비퍼의 좌표를 나타내는 두 정수 $x$, $y$

각 시나리오마다 한 줄씩, 카렐이 시작 위치에서 출발해 모든 비퍼를 방문하고 다시 시작 위치로 돌아오는 최소 이동 거리를 다음 형식으로 출력합니다.

The shortest path has length D

여기서 $D$는 최소 이동 거리입니다.

• $1 \le$ 세계의 크기 $\le 9$
• $1 \le$ 비퍼의 개수 $\le 8$
• $1 \le x, y \le$ 세계의 크기