Problem Name: Railroad Conflict
Problem Description: Nate U. Smith runs a railway company in a metropolitan area. In this metropolitan area, there is a rival railway company other than his railway company. The two companies are in competition with each other.
To make train operation easy in this metropolitan area, all routes are routes connecting the two end stations. In addition, to avoid the installation of level crossings, all routes are laid underground or elevated. Existing routes are either elevated over the entire line or underground over the entire line.
Recently, two blocks A and B in this metropolitan area have been actively developed, so Nate's company has decided to establish a new route between these blocks. The new route should have a route that connects A and B as well as the conventional route, but it is impossible to lay the entire line underground or elevated because there is another route on the way. Therefore, it was decided to lay a part of the route on the elevated and the rest on the underground. At the point where the new route intersects with the existing route, if the existing route is elevated, the new route is also elevated, and if the existing route is underground, the new route is also underground in order to facilitate transfer between the new route and the existing route. In addition, at the point where the new route intersects with the existing route of another company, in order to avoid interference by another company, if the existing route is elevated, the new route runs underground, and if the existing route is underground, the new route runs elevated. It is not particularly necessary to set A station and B station to either elevated or underground.
Of course, in order to set up an entrance or exit at the point where the new route moves from elevated to underground or from underground to elevated, it is necessary to spend money, so Nate, who thought that he needed your help, a programmer, called you to his company.
Your job is to create a program that, given the positions of A station and B station and information about existing routes, determines the minimum number of entrance/exit that must be provided on the new route.
The following figures show the input and output given as a sample.
Input
The first line of the input contains a single positive integer, which represents the number of data sets. Each dataset is given in the following format.
xa
ya
xb
yb
n
xs
1
ys
1
xt
1
yt
1
o
1
l
1
xs
2
ys
2
xt
2
yt
2
o
2
l
2
...
xs
n
ys
n
xt
n
yt
n
o
n
l
n
Here, (
xa
,
ya
) and (
xb
,
yb
) represent the coordinates of A station and B station, respectively.
N
is a positive integer of 100 or less representing the number of existing routes. (
xs
i
,
ys
i
) and (
ys
i
,
yt
i
) represent the coordinates of the starting and ending points of the
i
-th existing route.
o
i
is an integer representing the owner of the i-th existing route. This is either 1 or 0, indicating that the route is owned by the company or owned by another company, respectively.
l
i
is an integer indicating whether the i-th existing route is elevated or underground. This is also either 1 or 0, indicating that the route is elevated or underground, respectively.
The x and y coordinates appearing in the input range from -10000 to 10000 (both inclusive). Moreover, it can be assumed that the following conditions are satisfied for all lines, including the new line, in each dataset. Here, "very close" means that the