Help the People Been Trapped

Full Score of Fear, the Movie 12 of Detective Conan has been published recently.


Before going to the concert, Conan had been attacked and was unconscious. But Ran wasn’t aware of Conan’s disappearance. Then they went into the odeum, and the concert started.
Suddenly, the bombs in the odeum blasted and the whole building was on fire. All the audiences are trapped in the odeum, include Mouri Ran and Haibara Ai. Thousands of people are in danger now.

After the explosion, some walls have collapsed and blocked the way. Now Conan gets a map from the police, and he knows the location of all the hindrances. Also, he knows that Ran is a karate superior, and she can destroy some hindrances. (Horrific) As destroying the hindrance is a hard job, Conan wants to find a way to get out of the odeum crossing the least number of hindrances.

But the odeum is so large that it’s not an easy work to find that way. Can you help Conan and the people trapped in the odeum?

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 20 cases.
Each case contains an integer M on its first line, which is the number of the hindrances. 0<=M<=4000.
The next m lines describe m hindrances each. Each line contains four integers in each, x1, y1, x2, y2, means that there is a hindrance from (x1, y1) to (x2, y2). The hindrances will not cross each other, but they can meet at the end point.
The last line contains two integers, x, y, means that the people are trapped at point (x, y). You can assume that this point will not be on any of the hindrances.
Every coordinate is between -10,000 and 10,000.

For each case, print the least number of hindrances need to be destroyed. (If you need to cross an end point, it should be counted multiple times; look at the second sample for more details) Use the format in the sample.

3
0
0 0
12
0 0 2 0
2 0 4 0
0 2 2 2
2 2 4 2
0 4 2 4
2 4 4 4
0 0 0 2
0 2 0 4
2 0 2 2
2 2 2 4
4 0 4 2
4 2 4 4
1 1
6
0 2 1 0
0 2 -1 0
1 0 -1 0
0 2 -2 -1
0 2 2 -1
-2 -1 2 -1
0 1

Case 1: Need to destroy 0 hindrances.
Case 2: Need to destroy 1 hindrances.
Case 3: Need to destroy 2 hindrances.

2008 “Sunline Cup” National Invitational Contest