Астероїдні Рейнджери
Рік 2112, і людство підкорило сонячну систему. Корпус космічних рейнджерів встановив бази на кожному придатному для життя астероїді. Ваша задача як члена Міністерства комунікацій астероїдів полягає в тому, щоб забезпечити зв'язок між усіма базами астероїдів космічних рейнджерів з мінімальними витратами. Ви могли б встановити прямі комунікаційні зв'язки між кожною парою баз, але це було б надзвичайно дорого. Замість цього, ви прагнете встановити мінімальну кількість зв'язків, щоб кожна база могла надсилати повідомлення всім іншим, можливо, через одну або більше проміжних баз. Вартість будь-якого зв'язку прямо пропорційна відстані між двома базами, які він з'єднує, тому це не здається такою складною проблемою.
Однак є одна невелика складність. Астероїди мають тенденцію рухатися, тому дві бази, які зараз дуже близькі, можуть не бути такими в майбутньому. Тому з часом ви повинні бути готові перемикати свої комунікаційні зв'язки, щоб завжди мати найдешевшу систему ретрансляції. Перемикання цих зв'язків займає час і гроші, тому вас цікавить, скільки разів вам доведеться виконувати таке перемикання.
Кілька припущень полегшують ваше завдання. Кожен астероїд вважається однією точкою. Астероїди завжди рухаються лінійно з фіксованою швидкістю. Жоден астероїд ніколи не стикається з іншими астероїдами. Також будь-яка система ретрансляції, яка стає оптимальною в момент часу t ≥ 0, буде унікально оптимальною для будь-якого часу s, що задовольняє t < s < t+10. Початкова оптимальна система ретрансляції буде унікальною.
Вхідні дані
Кожен тестовий випадок починається з рядка, що містить ціле число n (2 ≤ n ≤ 50), яке вказує на кількість баз астероїдів. Далі йдуть n рядків, кожен з яких містить шість цілих чисел x, y, z, v_x, v_y, v_z. Перші три вказують початкове розташування астероїда (-150 ≤ x, y, z ≤ 150), а останні три вказують компоненти швидкості цього астероїда по осях x, y і z в одиницях простору за одиницю часу (-100 ≤ v_x, v_y, v_z ≤ 100).
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить номер випадку та кількість разів, коли систему ретрансляції потрібно налаштувати або змінити.