Минтранс сделал соответствующие выводы из своего железнодорожного эксперимента и решил перейти к строительству автобанов, так как это хорошо вписывалось в планы подготовки к Евро-2012. Было решено между городами построить сеть автобанов, причём с целью экономии средств эти автобаны должны быть строго прямыми отрезками. Естественно, что и скорость сообщения и время проезда на таких автобанах будет выше. Кроме того, было принято решение, что так как иногда какой-то автобан может закрываться на реконструкцию, построенная сеть дорог должна обеспечивать возможность доехать из одного города в другой даже при проведении подобной реконструкции. Также естественно, что количество таких дорог в сети должно быть минимально. Как всегда, нашлась ещё одна умная голова, которая предложила плату за проезд по автобану брать не при въезде на него, а только на перекрёстках. Вот теперь и ломают голову в Минтрансе: как построить подобную сеть с минимальным количеством дорог, но с максимальным количеством пунктов сбора средств за проезд? Ваша задача - написать программу, которая посчитает максимальное количество приносящих прибыль пунктов оплаты проезда по автобанам, а как строить саму сеть - уже будут рассчитывать работники Минтранса. Да, и ещё - уже приняты новые правила движения для автобанов, запрещающие в пунктах оплаты за проезд съезжать с одного автобана и продолжать движение по другому - не будем объяснять, исходя из каких экономических размышлений это было сделано... :) \InputFile В первой строке единственное натуральное число - количество тестовых случаев \textbf{T} (\textbf{T} ≤ \textbf{1000}). В последующих \textbf{T} строках также задано по одному натуральному числу \textbf{N} - количество городов в сети (\textbf{N} ≤ \textbf{32767}). \InputFile Для каждого тестового случая в отдельной строке вывести искомое максимальное количество пунктов сбора денег.