숨어야 한다

당신에게는 임무가 하나 주어졌다. 끝없이 펼쳐진 2차원 격자 위의 강하 지점 칸 (sx, sy) 로 인원을 보내고, 그 뒤 적에게 들키지 않도록 이동을 지원해 적 기지가 있는 칸 (gx, gy) 로의 잠입을 성공시키는 것이다. 당신은 이 중요한 임무의 잠입 역할을 잠입 전문가 시노비 코마에게 맡겼다.

시노비 코마는 상하좌우로 인접한 4칸 중 하나로 이동하기를 반복하며 적 기지를 향해 나아간다. 또한 임무를 신속히 수행하기 위해 강하 지점에서 적 기지까지 반드시 최단 거리로 이동한다.

사전 정찰에 따르면 이 2차원 격자 위에는 적 센서가 N개 있고, i번째 센서는 (xi, yi) 를 중심으로 한 변의 길이가 2ri + 1인 정사각형 영역, 즉 |x - xi| ≤ ri 이고 |y - yi| ≤ ri 를 만족하는 모든 칸 (x, y) 를 감시하고 있다. 시노비 코마는 하나 이상의 센서가 감시하는 영역에 들어가면 적에게 발각된다.

문제는 현재 센서 배치로는 시노비 코마가 최단 거리로 적 기지에 도달하지 못할 수도 있다는 점이다. 이 경우 당신은 지원 역할로서 센서를 파괴해야 한다. 위험과 비용을 줄이기 위해 파괴하는 센서의 개수는 가능한 한 적어야 한다.

예를 들어 입력 샘플의 네 번째 데이터 세트는 그림 C-1과 같다. 그림 C-2처럼 센서 3개를 제거하면 시노비 코마가 최단 거리로 적 기지에 도달할 수 있게 되고, 이 예에서 이것이 최소 개수이다.

그림 C-1 입력 샘플 네 번째 데이터 세트의 배치

그림 C-2 입력 샘플 네 번째 데이터 세트에서 최소 개수의 예

눈치가 빠른 당신이라면 알아차렸을 것이다. 어쩔 수 없이 센서에 탐지되는 시노비 코마보다, 센서에 탐지되지 않고 파괴할 수 있는 당신이 잠입 실력이 더 높다는 것을. 그렇다. 사실 시노비 코마는 자신을 잠입 전문가로 착각하고 있을 뿐인 평범한 사람이고, 잠입시키는 전문가 시노비 코마세는 바로 당신이다. 아무것도 모르는 시노비 코마가 눈치채지 못하도록 은밀히 필요 최소한의 센서를 파괴해, 마치 자신이 잠입 전문가인 것처럼 시노비 코마를 믿게 만드는 것이 잠입시키는 전문가로서 당신의 긍지이다. 우선 전문가로서 미리 비용을 산정하기 위해, 시노비 코마의 임무를 성공시키려면 최소 몇 개의 센서를 파괴해야 하는지 구하라.

입력은 100개 이하의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.

N
sx sy gx gy
x1 y1 r1
...
xN yN rN

첫째 줄은 센서의 개수 N (1 ≤ N ≤ 105)을 나타내는 정수로 이루어진다. 둘째 줄의 sx, sy 는 시노비 코마의 강하 지점 (sx, sy) 를, gx, gy 는 적 기지의 위치 (gx, gy) 를 나타내며, 1 ≤ sx, gx ≤ 1000, 1 ≤ sy, gy ≤ 1000 을 만족한다. 이어지는 N개 줄의 i번째 줄은 i번째 센서의 정보이며, 센서가 위치 (xi, yi) 를 중심으로 한 변의 길이가 2ri + 1인 정사각형 영역을 감시하고 있음을 나타낸다. 1 ≤ xi ≤ 1000, 1 ≤ yi ≤ 1000, 0 ≤ ri ≤ 1000 을 각각 만족한다. 여기서 (sx, sy) 와 (gx, gy) 는 반드시 다른 칸이다.

입력의 끝은 0 하나로 이루어진 줄로 나타낸다.

각 데이터 세트에 대해 시노비 코마가 (sx, sy) 에서 (gx, gy) 까지 센서 영역을 지나지 않고 최단 거리로 이동할 수 있게 하려면 파괴해야 하는 센서의 최소 개수를 한 줄에 출력하라.