Зона безпеки
Менеджер великої охоронної компанії має створити нову систему спостереження для різних об'єктів. Кожен об'єкт складається з N елементів, і кожен з них має своє охоронне коло. На межі системи спостереження повинен бути встановлений високовольтний паркан. Охоронна зона всередині паркану має бути цілісною. Крім того, всі об'єкти та їх охоронні кола повинні розташовуватися всередині охоронної зони. Охоронні кола різних об'єктів ніколи не перетинаються і не торкаються. Тепер менеджеру потрібна ваша допомога. Він просить вас визначити мінімальну необхідну довжину паркану.
Рисунок 1 - Ілюстрація першого та другого прикладу вхідних даних.
Вхідні дані
Перша стрічка вхідних даних містить кількість тестових випадків C (0 ≤ C ≤ 100). Перша стрічка кожного тестового випадку містить ціле число N: кількість об'єктів на поточному об'єкті (0 < N ≤ 25). Кожна з наступних N стрічок містить три цілі числа x_i, y_i та r_i, які описують об'єкт. Це координати i-го об'єкта та радіус необхідного охоронного кола для цього об'єкта. (|x_i|,|y_i| ≤ 100, 0 < r_i ≤ 100) (Центр охоронного кола навколо об'єкта є положенням самого об'єкта.)
Вихідні дані
Для кожного тестового випадку виведіть одну стрічку, що містить мінімальну довжину паркану для цього випадку. Ваш вихід повинен мати абсолютну або відносну похибку не більше 10^{-7}.