철도 충돌

Nate U. Smith는 대도시권의 철도 회사를 운영한다. 이 대도시권에는 그의 회사 외에도 경쟁 철도 회사가 있다. 두 회사는 서로 경쟁 관계에 있다.

이 대도시권에서는 열차 운행을 원활하게 하기 위해 모든 노선이 양 끝 역을 잇는 선분을 경로로 삼는다. 또한 건널목 설치를 피하기 위해 모든 노선은 고가 또는 지하에 놓인다. 기존 노선은 전 구간을 고가로 달리거나 전 구간을 지하로 달리는 두 가지 중 하나다.

그런데 최근 이 대도시권의 두 지구 A, B가 활발히 개발되면서 Nate의 회사는 이 두 지구 사이에 새 노선을 놓기로 결정했다. 새 노선도 기존 노선처럼 A, B를 양 끝으로 하는 선분을 경로로 삼으려 하지만, 경로 중간에 다른 노선이 있어서 전 구간을 고가나 지하 중 하나로만 놓을 수는 없다. 그래서 노선의 일부는 고가로, 나머지는 지하로 놓기로 했다. 이때 새 노선이 자사 기존 노선과 만나는 곳에서는 새 노선과 기존 노선 사이의 환승을 편하게 하기 위해 기존 노선이 고가면 새 노선도 고가로, 기존 노선이 지하면 새 노선도 지하로 달린다. 또한 새 노선이 타사 기존 노선과 만나는 곳에서는 타사의 방해를 피하기 위해 기존 노선이 고가면 새 노선은 지하로, 기존 노선이 지하면 새 노선은 고가로 달린다. A 역과 B 역을 각각 고가로 놓을지 지하로 놓을지는 따로 정해지지 않는다.

당연히 새 노선이 고가에서 지하로, 또는 지하에서 고가로 바뀌는 곳에는 출입구를 두어야 한다. 그런데 출입구를 두려면 비용이 들기 때문에 새 노선에 둘 출입구의 개수를 최소로 줄이고 싶다. 이를 위해서는 프로그래머인 당신의 도움이 필요하다고 생각한 Nate가 당신을 그의 회사로 불러들였다.

당신의 일은 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

여기서 (xa,ya)와 (xb,yb)는 각각 A 역, B 역의 좌표를 나타낸다. N은 기존 노선의 수를 나타내는 100 이하의 양의 정수이다. (xs**i,ys**i)와 (xt**i,yt**i)는 i번째 기존 노선의 시작점과 끝점의 좌표를 나타낸다. o**i는 i번째 기존 노선의 소유자를 나타내는 정수이다. 이는 1 또는 0이며, 1은 그 노선이 자사 소유임을, 0은 타사 소유임을 나타낸다. l**i는 i번째 기존 노선이 고가에 있는지 지하에 있는지를 나타내는 정수이다. 이 역시 1 또는 0이며, 1은 그 노선이 고가에 있음을, 0은 지하에 있음을 나타낸다.

입력에 나타나는 x 좌표와 y 좌표의 값은 -10000에서 10000 범위에 있다(양 끝도 범위에 포함된다). 또한 각 데이터셋에서 새 노선을 포함한 모든 노선에 대해 다음 조건이 성립한다고 가정해도 좋다. 여기서 두 점이 매우 가깝다는 것은 두 점 사이의 거리가 10-9 이하임을 나타낸다.

• 어떤 교점의 매우 가까운 곳에 다른 교점이 있지 않다.
• 어떤 노선의 끝점의 매우 가까운 곳을 다른 노선이 지나지 않는다.
• 두 노선의 일부 또는 전부가 겹치지 않는다.

각 데이터셋에 대해 최소한 두어야 하는 출입구의 개수를 한 줄에 출력한다.