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