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 Si has a power Pi. We define targets of a teleportation station A with power PA as : all the teleportation stations which are inside or on the border of a circle centered at A with a radius of PA.
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 Xs, Ys to an ending point Xe, Ye 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 Si. A teleportation station description consists of three integers Xi, Yi, Pi : the 2D coordinates of the teleportation station , and its power. The next line contains four integers: Xs, Ys, Xe, Ye : the 2d coordinates of a starting point and an ending point.
- 109 ≤ Xi, Yi, Xs, Ys, Xe, Ye ≤ 109
0 ≤ Pi ≤ 109
for each test case you have to print the minimum time required to move from the starting point to the ending point
## Input
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 Si. A teleportation station description consists of three integers Xi, Yi, Pi : the 2D coordinates of the teleportation station , and its power. The next line contains four integers: Xs, Ys, Xe, Ye : the 2d coordinates of a starting point and an ending point. - 109 ≤ Xi, Yi, Xs, Ys, Xe, Ye ≤ 109 0 ≤ Pi ≤ 109
## Output
for each test case you have to print the minimum time required to move from the starting point to the ending point
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $, let $ s_k \in \Sigma^* $ be a string of length $ n_k $, where $ \Sigma = \{a, b, \dots, z\} $, and $ 1 \leq n_k \leq 10^5 $.
**Constraints**
1. $ 1 \leq T \leq 5 $
2. For each $ k $, $ 1 \leq n_k \leq 10^5 $, and all characters in $ s_k $ are lowercase English letters.
**Objective**
For each string $ s_k $, define the set of operations:
- For each position $ i \in \{1, \dots, n_k\} $, and for each character $ c \in \Sigma $, let $ s_k^{(i,c)} $ denote the string obtained by replacing the character at position $ i $ with $ c $.
Let $ P(s) $ denote the number of distinct palindromic substrings in string $ s $.
Find:
1. $ M_k = \max_{i \in [n_k], c \in \Sigma} P(s_k^{(i,c)}) $
2. $ C_k = \left| \left\{ (i, c) \in [n_k] \times \Sigma \mid P(s_k^{(i,c)}) = M_k \right\} \right| $
Output $ (M_k, C_k) $ for each test case $ k $.