0060 - がんばれ。

問題

この国の鉄道会社は2社が競合関係にある。
この国では、電車の運行を容易にするため、すべての路線が両端の駅を 結んだ線分を経路としている。 また、踏切の設置をさけるためにすべての路線が高架または地下に 敷設されている。既存路線は、全線にわたり高架を走る、もしくは全線に わたって地下を走るかのいずれかである。

M田さんはあまり疲れたくないため、家から学校まで行くのに一直線上に 新幹線を設置したいと考え、家の駅から学校の駅の間に新しいプライベート 路線を設けたいと考えた。しかし、一直線上に路線を設置したくても 経路の途中に別の路線があるため、高架あるいは地下に全線を敷設する ことができない。そこで、路線の一部を高架に、残りの部分を地下に 敷設することにした。このとき、新幹線がM田さんがいつも利用している A社の既存路線と交わるところでは、新幹線と既存路線との間の乗り継ぎ を便利にするために既存路線が高架なら新幹線も高架にし、既存路線が 地下ならば新幹線も地下を走るようにする。また、M田さんが嫌っている B社の既存路線と交わるところでは、B社による妨害をさけるために 既存路線が高架なら新幹線は地下にし、既存路線が地下なら新幹線は 高架を走るようにする。家の駅および学校の駅をそれぞれ高架あるいは 地下のいずれに設けるかは特に問わないものとする。

この条件だと、新幹線が高架から地下に、または地下から高架に移る ところには出入口を設ける必要がある。ところが、出入口を設けるため には費用がかかってしまう。M田さんも学生でまだお金も少ないため、 新幹線に設ける出入口の個数を最小限に抑えなければならない。

プログラマである君に助けてほしい。
あなたの仕事は、家の駅、学校の駅の位置、そして、既存路線(A社、B社) に関する情報が与えられたときに、新幹線において最低限設ける必要が ある出入口の個数を求めるプログラムを作成することである。

以下の図は、サンプルとして与えた入力および出力の内容を示している。

入力

入力の先頭行には正の整数がひとつ与えられ、これはデータセットの 個数を表す。それぞれのデータセットは次の形式で与えられる。

xa ya xb yb
n
xs1 ys1 xt1 yt1 o1 l1
xs2 ys2 xt2 yt2 o2 l2
   :
xsn ysn xtn ytn on ln

1行目には4つの整数xa,ya,xb,ybが与えられる。 (xa,ya) : 家の駅の座標 (xb,yb) : 学校の駅の座標 2行目には1つの整数nが与えられる。 n : 既存路線の数 3行目からn+2行目には既存路線の情報が与えられる。 6つの整数xs_i,ys_i,xt_i,yt_i,o_i,l_iが与えられる。 (xs_i,ys_i) : i番目の既存路線における始点の座標 (xt_i,yt_i) : i番目の既存路線における終点の座標 o_i : i番目の既存路線の所有者 1または0のいずれかが与えられる。 1はそのA社の路線であり、0はそのB社の路線である。 l_i : i番目の既存路線が高架または地下のいずれであることを表す整数 1または0のいずれかが与えられ、1はその路線が高架にあり、0はその路線が地下にあることを示す。

制約・条件

入力で与えられる座標(xまたはy)はすべて-10000から10000の範囲にある。 Nは100以下の正の整数である。

すべての路線に対して、以下の条件を満たす。

• ある交点の非常に近くに別の交点があることはない。
• ある路線の端点の非常に近くを別の路線が通ることはない。
• 2つの路線の一部または全部が重なることはない。

出力

それぞれのデータセットに対して、最低限設けなければならない出入口の個数を1行に出力しなさい。

入出力例

入力例1

2
-10 1 10 1
4
-6 2 -2 -2 0 1
-6 -2 -2 2 1 0
6 2 2 -2 0 0
6 -2 2 2 1 1
8 12 -7 -3
8
4 -5 4 -2 1 1
4 -2 4 9 1 0
6 9 6 14 1 1
-7 6 7 6 0 0
1 0 1 10 0 0
-5 0 -5 10 0 1
-7 0 7 0 0 1
-1 0 -1 -5 0 1

出力例1

1
3