Beer Land

King ACM 2002 inherited some open land and some money. The terms of the will require the heir to found $n$ towns and to build the fewest possible two-way roads between them so that one can still travel from any town to any other town even if any single road is closed for repair. Every road must be a geometrically straight segment joining two towns, and this survivability must be achieved by riding roads from end to end -- a traveller never leaves a road partway to switch onto another.

Because the soil is rich, the inhabitants will brew beer, and the king wants a beer stand at every crossroad, where a crossroad is a point at which two or more roads intersect. Only one stand is built per crossroad, so even if three, four, or twenty roads meet at a single point, there is still just one place for a stand there. The king may freely choose where to place the towns and how to lay the roads. Advise him so that the number of beer stands is as large as possible.

The first line contains the number of test cases. Each of the following lines contains a single integer $n$ ($1 \le n \le 32767$), the number of towns to be built.

For each test case, print on its own line the maximum number of beer stands that can be built.