409898: GYM103828 K No Server? !Problem

AbdulQader is a tech genius. he spent many years mastering the Art of Networking, so when he knew the SCPC needs volunteers for IT support, he signed in right away.

During the contest, a sudden error caused the server to crash. having no time to set up a new server, AbdulQader decides to connect every two computers $$$directly$$$.

The contest has $$$n$$$ computers and a central switch of $$$\frac{n(n-1)}{2}$$$ connection points lined up in a row (numbered from $$$1$$$ to $$$\frac{n(n-1)}{2}$$$). To connect any two computers $$$directly$$$ you have to connect them to the same connection point. Each connection point can be connected to at most two computers.

The latency $$$X_i$$$ of a computer $$$i$$$ equals $$$X_i = p_e - p_s$$$ where :

• $$$p_s$$$ $$$(1 \le p_s \le \frac{n(n-1)}{2})$$$ is the first connection point used by computer $$$i$$$.
• $$$p_e$$$ $$$(1 \le p_e \le \frac{n(n-1)}{2})$$$ is the last connection point used by computer $$$i$$$.

AbdulQader knows that as $$$latency$$$ gets bigger the connection gets slower, so he wants to connect computers in a way to make the sum of total $$$latency$$$ for all the computers $$${\sum_{i = 1}^n X_i}$$$ as minimum as possible. Can you help him find that order?

Note that you have to connect each two exactly once.

The first line of the input contains a single integer $$$T$$$, the number of test cases.

The next $$$T$$$ lines each contains a single integer $$$n$$$ ($$$2 \le n \le 500$$$), the number of computers.

The sum of $$$n$$$ over all test cases doesn't exceed $$$500$$$.

For each test case print $$$m=\frac{n(n-1)}{2}$$$ lines where the $$$i^{th}$$$ line contain two integers $$$a,b$$$ $$$(1 \le a,b \le n)$$$ which represents a connection between computers $$$a$$$ and $$$b$$$ at the connection point $$$i$$$.

1
3

2 1
3 2
1 3

We can connect: computers 1 and 2 at connection point 1, computers 2 and 3 at connection point 2, computers 1 and 3 at connection point 3, so that total $$$latency$$$ = 2 + 1 + 1 = 4