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.
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
Castle 1: 14 Castle 2: 2