Prime Village

The residents of Prime Village follow a very unusual rule: they go to a place only if the distance to it is a prime number.

Seungwook, a resident of Prime Village, has an errand in village A, which is far from Prime Village, so he has to travel there. He would like to go from Prime Village to village A in one move, but he cannot if the distance between the two villages is not prime. In that case he has to pass through other villages on the way. He can move to an intermediate village only if the distance from his current position to that village is also prime.

The positions of Prime Village, the villages he can pass through, and village A are given as points on the coordinate plane. Help Seungwook find the shortest route to village A that follows the rule of Prime Village.

The distance between two villages is taken as the integer part of the distance between the two points. For example, a distance of $3.1415$ is truncated and treated as $3$. The truncated value is used both to test for primality and when adding up the distances traveled.

The first line contains the position $(X_1, Y_1)$ of Prime Village and the position $(X_2, Y_2)$ of village A, in the order $X_1$ $Y_1$ $X_2$ $Y_2$.

The second line contains $N$ ($0 \le N \le 4000$), the number of villages he can pass through.

Each of the next $N$ lines contains the position $X_3$ $Y_3$ of one village he can pass through.

Every coordinate is an integer whose absolute value does not exceed $3000$.

Print the total distance of the shortest route to village A that follows the rule of Prime Village. The total is the integer sum of the truncated distances of the individual moves.

If there is no way to reach village A while following the rule, print $-1$.

In the first example, the distance between Prime Village $(1, 2)$ and village A $(5, 4)$ is $\sqrt{20} \approx 4.47$, which is treated as $4$, and $4$ is not prime. Passing through village C $(4, 1)$ makes both moves $\sqrt{10} \approx 3.16$, that is $3$, so the total distance is $6$.