Problem D: Treasure Castle

The treasure hunting chapter of iCORE (international Conference of Revolver Enthusiasts) has just acquired a map of a castle which is now in ruins but its cellars contain an unimaginable treasure. The map is drawn on an orthogonal integer lattice. The coordinates of the lower left corner of the lattice are (-10000, -10000) while the coordinates of the upper right corner are (10000, 10000). The external walls of the castle are either horizontal or vertical and always span a distance between the towers of the castle. Walls do not cross and if they have a point in common then it is a tower of the castle. Exactly two walls meet at each tower. The towers are located at grid points. The grid lines not outside the walls of the castle correspond to underground corridors. The map indicates that at one of the grid points there is an entrance to the underground corridors and that at another grid point the long sought for treasure is to be found.

Your task is to compute the shortest path that leads from the entrance to the treasure through the underground corridors. You can switch corridors at grid points.

The attached figure illustrates the castle of the first case of sample input.

Your program should read input from file named castle.dat. The input file contains multiple cases. The first line of each case contains an integer number n, 4 ≤ n ≤ 5000, which is the number of towers in the castle. In each of the next n lines there are two integers giving the x and y coordinates of a tower. There is a wall between any two subsequent towers and there is a wall between the first and the last listed towers. The last two lines of input give the x and y integer coordinates of the entrance and the treasure, respectively.

The input is terminated by a case with n = 0 and this case should not be processed.

For each case of input, output one line following the format from the sample output. The castles are numbered by subsequent integers starting from 1. For each castle, print its number followed by a colon and after one space print one integer giving the shortest distance in grid units between the entrance and the treasure along the underground corridors.

Sample input

10
9 6
9 2
12 2
12 9
2 9
2 1
8 1
8 3
4 3
4 6
11 5
3 1
5
0 0
0 1
0 2
2 2
2 0
2 2
1 1
0

Output for sample input

Castle 1: 14
Castle 2: 2

K. Diks, adapted by P. Rudnicki