有一个 $$$3n \times 3n$$$ 点的网格,由所有整数点 $$$(x,y)$$$ 组成,使得 $$$1 \le x,y \le 3n$$$。
查找 最大 满足以下条件的三角形集合:
- 每个三角形的顶点都位于 正好三个 网格上的 点。
- 每个三角形的面积正好为 $$$\frac{1}{2}$$$。请注意,他们 不 必须是直角三角形。
- 没有两个三角形共享公共交点,包括它们的顶点。
如果存在多个最大的此类三角形集合,则可以输出其中任何一个。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 30$$$)。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 166$$$)。
保证所有测试用例的$$$n^2$$$总和不超过$$$166^2$$$。
输出
输出 最大 一条线上三角形集合的大小 $$$m$$$ ($$$0 \le m \le 3n^2$$$)。
然后,按以下格式输出 $$$m$$$ 行:
- $$$x_{i,1}\;y_{i,1}\;x_{i,2}\;y_{i,2}\;x_{i,3}\;y_{i,3}$$$:第 $$$i$$$ 个三角形的顶点为 $$$(x_{i,1},y_{i,1})$$$, $$$(x_{i,2},y_{i,2})$$$,$$$(x_{i,3},y_{i,3})$$$。
您可以按任意顺序(顺时针或逆时针)输出一个三角形的顶点。
如果您的输出满足所有条件并且给定的最大尺寸正确,则您的输出将被接受。
示例
输入复制
212
输出复制
2 1 1 1 2 2 1 2 3 3 2 3 3 12 1 1 1 2 2 1 2 2 3 2 3 1 1 3 1 4 2 3 2 4 3 4 3 3 1 5 1 6 2 5 2 6 3 6 3 5 4 1 4 2 5 1 5 2 6 2 6 1 4 3 4 4 5 3 5 4 6 4 6 3 4 5 4 6 5 5 5 6 6 6 6 5
注意
在第一个测试用例中,示例输出具有 $$$2$$$ 三角形,如下图所示:
在第二个测试用例中,示例输出有 $$$12$$$ 三角形,如左图所示:
![]() | ![]() |
由于三角形不需要是直角三角形,因此右侧图像中显示的三角形组也将被视为有效。

