Must Stay Hidden

You have been given a mission. You must send a person to a drop point cell (sx, sy) on an infinite two-dimensional grid, then support their movement so that the enemy does not notice, and make the infiltration into the cell (gx, gy) where the enemy base is located succeed. You entrusted the infiltration role in this important mission to the infiltration professional Shinobi Komiya.

Shinobi Komiya repeatedly moves to one of the four cells adjacent up, down, left, or right, heading for the enemy base. Also, to carry out the mission quickly, they always move along a shortest path from the drop point to the enemy base.

According to prior reconnaissance, there are N enemy sensors on this two-dimensional grid, and the i-th sensor covers a square region centered at (xi, yi) with side length 2ri + 1, that is, all cells (x, y) satisfying |x - xi| ≤ ri and |y - yi| ≤ ri. Shinobi Komiya is discovered by the enemy upon entering a region covered by one or more sensors.

The problem is that with the current sensor placement, Shinobi Komiya may not be able to reach the enemy base along a shortest path. In this case, you must destroy sensors as the support role. To reduce risk and cost, you want to destroy as few sensors as possible.

For example, the fourth dataset of the input samples is as shown in Figure C-1. By removing three sensors as in Figure C-2, Shinobi Komiya can reach the enemy base along a shortest path, and in this example this is the minimum number.

Figure C-1 Placement in the fourth dataset of the input samples

Figure C-2 Example of the minimum number in the fourth dataset of the input samples

If you are sharp, you have noticed. Compared with Shinobi Komiya, who inevitably gets detected by sensors, you, who can destroy sensors without being detected, have higher infiltration skill. That is right. In fact, Shinobi Komiya is an ordinary person who merely mistakes themself for an infiltration professional, and you are the infiltration-enabling professional Shinobi Komase. Secretly destroying the minimum necessary sensors without the unknowing Shinobi Komiya noticing, and making Shinobi Komiya believe that they are an infiltration professional, is your pride as an infiltration-enabling professional. First, as a professional estimating the cost in advance, find the minimum number of sensors that must be destroyed for Shinobi Komiya's mission to succeed.

The input consists of at most 100 datasets. Each dataset is given in the following format.

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

The first line consists of an integer representing the number of sensors N (1 ≤ N ≤ 105). In the second line, sx, sy represent Shinobi Komiya's drop point (sx, sy), and gx, gy represent the position of the enemy base (gx, gy), satisfying 1 ≤ sx, gx ≤ 1000, 1 ≤ sy, gy ≤ 1000. The following N lines, the i-th line, contain information about the i-th sensor, indicating that the sensor covers a square region centered at position (xi, yi) with side length 2ri + 1. They satisfy 1 ≤ xi ≤ 1000, 1 ≤ yi ≤ 1000, 0 ≤ ri ≤ 1000, respectively. Here, (sx, sy) and (gx, gy) are always different cells.

The end of the input is indicated by a line consisting of a single zero.

For each dataset, output in one line the minimum number of sensors that must be destroyed so that Shinobi Komiya can move from (sx, sy) to (gx, gy) along a shortest path without passing through sensor regions.