Highways#1982
You are building a road network! You have cities that you need to connect with straight roads. You want to use the smallest number of roads possible, but here's the fun part: some roads can cross each other!
Every time two roads cross, you can put a special checkpoint at that crossing point. Your goal is to build the road network in such a way that you get the MAXIMUM number of crossing points (checkpoints).
Remember:
Roads must be straight lines
Use the minimum number of roads to connect all cities
You want as many road crossings as possible
The first line has a number (T \leq 1000) — how many different city networks you need to solve. The next lines each have a number (N \leq 32767) — the number of cities in that network.
For each network, print one number: the maximum number of crossing points you can get.
Example 1