Мінтранс зробив відповідні висновки зі свого залізничного експерименту і вирішив перейти до будівництва автобанів, так як це добре вписувалось у плани підготовки до Євро-2012. Було вирішено між містами побудувати мережу автобанів, причому з метою економії коштів ці автобани повинні бути строго прямими відрізками. Звичайно, що і швидкість пересування і час проїзду на таких автобанах буде рівнем вище. Крім того, було прийнято рішення, що так як інколи якийсь автобан може закриватись на реконструкцію, побудована мережа доріг повинна забезпечувати можливість доїхати від одного міста до іншого навіть при проведенні подібної реконструкції. Також зрозуміло, що кількість таких доріг у мережі повинна бути мінімальною. Як завжди, знайшлась ще одна розумна голова, яка запропонувала плату за проїзд по автобану брати не при в'їзді на нього, а лише на перехрестях. Ось тепер і ламають голови у Мінтрансі: як побудувати подібну мережу з мінімальною кількістю доріг, але з максимальною кількістю пунктів збору коштів за проїзд? Ваша задача - написати програму, яка підрахує максимальну кількість пунктів оплати проїзду по автобанам, які приносять прибуток, а як будувати саму мережу - вже будуть проектувати працівники Мінтрансу. Да, і ще - вже прийнято нові правила дорожнього руху для автобанів, які забороняють у пунктах оплати за проїзд з'їжджати з одного автобану і продовжувати рух по іншому - не будемо пояснювати, виходячи з яких економічних міркувань це було зроблено... :) \InputFile У першому рядку єдине натуральне число - кількість тестових випадків \textbf{T} (\textbf{T} ≤ \textbf{1000}). У наступних \textbf{T} рядках також задано по одному натуральному числу \textbf{N} - кількість міст у мережі (\textbf{N} ≤ \textbf{32767}). \OutputFile Для кожного тестового випадку у окремому рядку вивести шукану максимальну кількість пунктів збору грошей.