Transport Ministry to draw appropriate conclusions from their train experiment and decided to go to the construction of highways, because it fitted well into the plans of preparations for Euro 2012. It was decided to build a network between the cities of highways, and to save money, these highways should be strictly straight lines. Naturally, the speed of communication and travel time on these motorways will be higher. In addition, it was decided that, since sometimes a highway may be closed for reconstruction, built a road network must be capable to get from one city to another, even during this reconstruction. It is also natural that the number of such roads in the network should be minimal. As always, there were still a wise head, which suggested that the fare on the highway does not take the entrance to it, but only at intersections. So now scratching their heads in the Ministry of Transport: how to build such a network with a minimal number of roads, but the maximum number of points of raising fares? Your task - to write a program that decides the maximum number of revenue-generating items fare on the Autobahn, and how to build the network itself - will have to count employees of Ministry of Transport. Yes, and more - have already adopted new rules of the road for the motorway, prohibiting paragraphs fare pull over a highway and continue on to another - will not explain the basis of which economic thinking has been done ... :) \InputFile The first line of a unique natural number - the number of test cases \textbf{T} (\textbf{T} ≤ \textbf{1000}). In the following \textbf{T} lines are also given one to a natural number \textbf{N} - the number of cities in the network (\textbf{N} ≤ \textbf{32767}). \OutputFile For each test case on a separate line to derive the desired maximum number of collection points for money.