Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

Now, the war is coming, no one want to fight with others, but you have to when you are facing.

As the king of a country, you should defend your country. The condition is that “There are N enemy armies around you, you have two towers and you want to build cannon on each tower to cover all the enemy armies”. The cannon has an “attack distance” R with a cost of R^2.

You are facing a problem, to cover all the armies and make the cost R1^2 + R2^2 minimal, where R1 and R2 are the attack distance of the two towers.

As the king of a country, you should defend your country. The condition is that “There are N enemy armies around you, you have two towers and you want to build cannon on each tower to cover all the enemy armies”. The cannon has an “attack distance” R with a cost of R^2.

You are facing a problem, to cover all the armies and make the cost R1^2 + R2^2 minimal, where R1 and R2 are the attack distance of the two towers.

The first line contains an integer t, number of test cases, following with t groups of test cases described as following.

For each case, the first line contains four integers: x1, y1, x2, y2, the Coordinates of the two towers.

The next line is an integer n, the number of enemy armies, following with n lines of coordinates: x, y, which is the coordinate of a group of enemy army, where:

t <= 100

1 <= n <= 100000,

-1000 <= x, y <= 1000

-1000 <= x1, y1, x2, y2 <= 1000

For each case, the first line contains four integers: x1, y1, x2, y2, the Coordinates of the two towers.

The next line is an integer n, the number of enemy armies, following with n lines of coordinates: x, y, which is the coordinate of a group of enemy army, where:

t <= 100

1 <= n <= 100000,

-1000 <= x, y <= 1000

-1000 <= x1, y1, x2, y2 <= 1000

提交代码