Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2761
Help Lin to walk less

Time Limit: 10 Seconds      Memory Limit: 32768 KB

In Lin's city, there are a lot of streets, which are either horizontal or vertical. Now she wants to visit her friend, and wonders how to there as short as possible. As her friend, you are asked to help her.

Input

First you will get a number N which is the number of test cases, followed by N test block. There is a break line between two cases. For each block, first is a number M(1 <= M <= 200) identifies the number of streets. Then M lines follow, each consists of four integers represent the two ends of street. It is guaranteed that none of the streets will be overlapped by the other one. The last line has four integers, the first two are coordinates of Lin's home, and the second two are coordinate of Lin's friend's home, both Lin and her friend's houses are on one of the above streets.

Output

First you should output "Case i:" identify the number of case. On the next line, if Lin could get her friend's home, output the least integer that Lin should walk, otherwise output -1.

Sample Input

2
4
1 0 1 3
2 0 2 3
0 1 3 1
0 2 3 2
0 1 0 2

5
1 0 1 3
2 0 2 3
0 1 3 1
0 2 3 2
4 0 4 3
0 1 4 1

Sample Output

Case 1:
3
Case 2:
-1

Author: PAN, Bo
Source: ZOJ Monthly, September 2006
Submit    Status