{"raw_statement":[{"iden":"statement","content":"You have moved to a city called teleportia and you are looking for a job. \n\nThis 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 : \n\nEach 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. \n\nOnce you enter a teleportation station you'll have to wait for 2 seconds until you are teleported to one of its target teleportation stations. \n\nThe 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 ? \n\n The input starts with T the number of test Cases. \n\nEach test case starts with a number n (0 ≤ n ≤ 100), the number of teleportation stations. \n\nThen 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. \n\n - 109 ≤ Xi, Yi, Xs, Ys, Xe, Ye ≤ 109 \n\n0 ≤ Pi ≤ 109\n\nfor each test case you have to print the minimum time required to move from the starting point to the ending point \n\n"},{"iden":"input","content":" 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"},{"iden":"output","content":"for each test case you have to print the minimum time required to move from the starting point to the ending point "},{"iden":"examples","content":"Input135 5 59 5 311 7 24 6 11 8Output7"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor 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 $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 5 $  \n2. For each $ k $, $ 1 \\leq n_k \\leq 10^5 $, and all characters in $ s_k $ are lowercase English letters.\n\n**Objective**  \nFor each string $ s_k $, define the set of operations:  \n- 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 $.  \n\nLet $ P(s) $ denote the number of distinct palindromic substrings in string $ s $.  \n\nFind:  \n1. $ M_k = \\max_{i \\in [n_k], c \\in \\Sigma} P(s_k^{(i,c)}) $  \n2. $ C_k = \\left| \\left\\{ (i, c) \\in [n_k] \\times \\Sigma \\mid P(s_k^{(i,c)}) = M_k \\right\\} \\right| $  \n\nOutput $ (M_k, C_k) $ for each test case $ k $.","simple_statement":"Given a string of lowercase letters, replace exactly one character with any lowercase letter to maximize the number of distinct palindromic substrings. Output the maximum number achievable and how many different ways (replacements) achieve that maximum.","has_page_source":false}