Автобани#1982
Ти будуєш мережу доріг! У тебе є міст, які потрібно з'єднати прямими дорогами. Ти хочеш використати якомога менше доріг, але ось цікава частина: деякі дороги можуть перетинатися одна з одною!
Кожного разу, коли дві дороги перетинаються, ти можеш поставити спеціальний контрольний пункт у точці перетину. Твоя мета — побудувати мережу доріг так, щоб отримати МАКСИМАЛЬНУ кількість точок перетину (контрольних пунктів).
Пам'ятай:
Дороги мають бути прямими лініями
Використовуй мінімальну кількість доріг для з'єднання всіх міст
Ти хочеш якомога більше перетинів доріг
У першому рядку число (T \leq 1000) — скільки різних мереж міст потрібно розв'язати. У наступних рядках міститься по одному числу (N \leq 32767) — кількість міст у цій мережі.
Для кожної мережі виведи одне число: максимальну кількість точок перетину, яку можна отримати.
Приклад 1