Collecting Beepers

Karel is a robot living in a rectangular coordinate system where every position is given by a pair of integer coordinates $(x, y)$. A number of beepers are placed throughout her world, and Karel must pick all of them up. Karel can only move along the $x$ and $y$ axes, never diagonally. Moving to an adjacent position costs one unit of distance, so the travel distance between two positions equals their Manhattan distance (the sum of the absolute differences of their coordinates).

Karel starts at her starting position, must visit every position that holds a beeper, and then return to her starting position. Find the minimum total length of the path Karel travels. The beepers may be visited in any order.

The first line contains the number of scenarios. Each scenario is given as follows:

• A line with two integers: the size of the world (x-size and y-size).
• A line with two integers $x$ and $y$: Karel's starting position.
• A line with one integer $n$: the number of beepers.
• $n$ following lines, each with two integers $x$ and $y$: the coordinates of a beeper.

For each scenario, print one line giving the minimum distance Karel must travel to leave her starting position, visit every beeper, and return to the starting position, in the form:

The shortest path has length D

where $D$ is the minimum distance.

• $1 \le$ size of the world $\le 9$
• $1 \le$ number of beepers $\le 8$
• $1 \le x, y \le$ size of the world