龙魂合一萨坎与晶石
题号：NC20896
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

「文词只是浪费时间。 毁灭这语言人人都懂。」           ——萨坎沃

       萨坎重回乌金之眼，他发现乌金之眼正因之前的交战被开启。他思索着主人的目的，突然发现巨龙形态下的自己可以读懂晶石上的铭文。他变成巨龙，驱散了另一条堕落的龙魂，阅读了晶石上的神秘铭文。他具体读到了什么我们不得而知，我们只知道，阅读铭文后的萨坎只想切碎所有的晶石。
       浮在空中的晶石排列成了一个 n x n 的方格阵。每个单位边长的方格内有一颗晶石。萨坎能做的是选择两个不同的落在方格阵边界的交点，然后用剑沿着这两点连线割下去。如果一个方格被割断（只割到顶点或边界不算割断），那么这个方格内的晶石将失去能量。

i2UxsA.png

       如上图所示，这是一个 3 x 3 的方格阵。其中橙色部分表示被割断的方格；深红色线表示割下的路径。每个交点的坐标标记在其附近。
       经过交战，萨坎剩余的能量只够切割 n+1 次。由于种种原因，萨坎必须切恰好 n+1 刀，并且萨坎所切的 n+1 刀中，不能有任何两刀平行。有着丰富经验的萨坎在砍完 n+1 刀之后所有的晶石都失去了能量。
       现在请聪明的你也学着像萨坎那样，在这个 n x n 的方格中，切恰好 n+1 刀，使所有方格都能被割断。

输入描述:

第一行一个正整数 T ，表示有 T 组测试数据。
接下去每组测试数据输入一行，包含一个正整数 n 。

输出描述:

每个测试数据输出 n+1 行，每行四个整数 px, py, qx, qy ，表示一条由点 (px, py) 和点 (qx, qy) 连成的直线。点 (px, py) 和点 (qx, qy) 必须落在方格阵的边界上，且两点不能相同。
每行的四个整数之间请用一个空格隔开，行末请不要添加多余空格。文末请不要输出多余信息。
示例1

输入

复制 
1
2

输出

复制 
0 0 1 2
1 2 2 0
0 0 2 0

说明

分割方案如下图所示。

备注:

1 ≤ N ≤ 2000
1 ≤ T ≤ 20