题意

给您一个整数 \(n\)。你在网格中选择 $n 个单元格 \((x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\)，其中\(1\le x_i\le n\)和\(1\le y_i\le n\)。

让 \(\mathcal{H}\) 成为任意一对单元格之间不同的曼哈顿距离的集合。你的任务是最大化 \(\mathcal{H}\) 的大小。注释中给出了集合及其构造的例子。

如果存在不止一个解，你可以输出任意一个。

单元 \((x_1,y_1)\) 和 \((x_2,y_2)\) 之间的曼哈顿距离等于 \(|x_1-x_2|+|y_1-y_2|\)。

观察及思考

首先写一个打表程序，以及测试 \(n\) 的每种取值时的答案
把打表出来的各种情况以及样例搞进去后，发现有一种情况对于 \(n \geq 4\) 时，每次 \(\mathcal{H}\) 集合都会稳定多出 \(2 \times n - 3\) 和 \(2 \times n - 2\) , 考虑以此构造。

发现这两个数只有在左上角，右下角，以及左上角右边 \(1\) 个位置时才会出现这种贡献，所以理所当然地想到只需要如下构造即可：

首先填满 \((1,1) (1,2)\)
然后从 \(i=3\) 开始，填满对角线即可

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int _;
    cin >> _;
    while (_--)
    {
        int n;
        cin >> n;
        cout << "1 1\n1 2\n";
        for (int i = 3; i <= n; i++)
            cout << i << " " << i << "\n";
        puts("");
    }
}