402798: GYM100883 I Teleportia

You have moved to a city called teleportia and you are looking for a job.

This city has a network of streets such that every two streets are either parallel or perpendicular and the distance between every two consecutive parallel streets is 1 meter. So you can consider the network of streets as an infinite 2D grid. The scientists in this city invented an advanced teleportation system , it consists of a set of teleportation stations, each station is located on an intersection of two streets the teleportation stations work as follows :

Each teleportation station S_i has a power P_i. We define targets of a teleportation station A with power P_A as : all the teleportation stations which are inside or on the border of a circle centered at A with a radius of P_A.

Once you enter a teleportation station you'll have to wait for 2 seconds until you are teleported to one of its target teleportation stations.

The government is planning to develop a system that finds the minimum time required to go from a starting point X_s, Y_s to an ending point X_e, Y_e considering an average person walks with a speed of 1 meter per second. since you are a programmer who is looking for a job , can you implement this system ?

The input starts with T the number of test Cases.

Each test case starts with a number n (0 ≤ n ≤ 100), the number of teleportation stations.

Then n lines follow each describing a teleportation station S_i. A teleportation station description consists of three integers X_i, Y_i, P_i : the 2D coordinates of the teleportation station , and its power. The next line contains four integers: X_s, Y_s, X_e, Y_e : the 2d coordinates of a starting point and an ending point.

 - 10⁹ ≤ X_i, Y_i, X_s, Y_s, X_e, Y_e ≤ 10⁹

0 ≤ P_i ≤ 10⁹

for each test case you have to print the minimum time required to move from the starting point to the ending point

1
3
5 5 5
9 5 3
11 7 2
4 6 11 8

7