I've just completed a mission inside ICPC Castle in the enemy country,
and am leaving the castle through the underground escape route dug in advance.
However, there are n watchtowers placed at equal intervals in the castle,
and I must reach the entrance of the escape route without
being noticed by the guards in the watchtowers.
The yard of the castle has a rectangular shape of 100n × 100.
Let the coordinates of the back left corner be (0, 0) and
the coordinates of the front right corner be (100n, 100).
The watchtowers are numbered from 1 to n, and the
kth watchtower is located at the coordinates (100k − 50, 50).
I am currently at the coordinates (x_{1}, y_{1}),
and I want to move to the coordinates (x_{2}, y_{2}),
where the entrance of the escape route is located, in the shortest possible time.
Should I move too fast near a watchtower, the guards might notice the footsteps.
Strictly saying, I must not move faster than
D^{2} per second, where D is the distance
to the nearest watchtower.
I'm wondering how long it takes to reach the entrance of the escape route.
For example, when there is one watchtower and the coordinates of the starting
location (current location) and the goal location (the entrance of the escape route)
are (5, 6) and (78, 90), respectively,
the optimal route is as shown in Figure H1.
For another example, when there are two watchtowers and the coordinates of the starting
location and the goal location are (85, 70) and (115, 30), respectively,
the optimal route is as shown in Figure H2.
These are corresponding to the first two datasets in the Sample Input.


Figure H1: The optimal route for the first dataset

Figure H2: The optimal route for the second dataset

The input consists of multiple datasets, each in the following format.
n
x_{1} y_{1}
x_{2} y_{2}
n is the number of watchtowers.
n is a positive integer not exceeding 10^{7}.
(x_{1}, y_{1}) gives the coordinates of the starting location, and
(x_{2}, y_{2}) gives the coordinates of the goal location.
x_{1} and x_{2} are integers between 0 and 100n, inclusive.
y_{1} and y_{2} are integers between 0 and 100, inclusive.
The coordinates of the starting and goal locations are different.
The coordinates of the starting and goal locations are also different from those of any watchtowers.
The end of the input is indicated by a line containing five zeros.
The number of datasets in the input is at most 1000.