在一个雨天，Lech 和 Grzegorz 在玩多米诺骨牌来消磨时间。他们的多米诺骨牌套装比普通的要大一些：它包含 $\frac{n(n+1)}{2}$ 个骨牌，每一块由两个半块组成，每个半块上有一个整数。这些骨牌的编号为 $(1, 1), (1, 2), \dots, (1, n), (2, 2), (2, 3), \dots, (n, n)$。

由于玩家很快就厌倦了遵循常规规则，他们开始思考一些更有挑战性的玩法。Grzegorz 想出了一个主意：将所有的骨牌放在一起，使得对于每一个整数，带有该整数的半块所占据的区域是连通的（所有的 $1$ 连在一起，所有的 $2$ 连在一起，以此类推）。他们开始尝试摆放这些骨牌，但很快发现这非常困难。“我知道我们该怎么做了！”，Lech 邪恶地笑道，“让我们把这个任务交给我们的学生吧！”。

你需要将所有骨牌放置在一个划分为单位正方形的大棋盘上。每块多米诺骨牌应恰好占据两个单位正方形，每个正方形包含一个数字。骨牌可以水平或垂直放置。骨牌之间不能重叠。如果两个单位正方形共享一条边，则认为它们是连通的。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 50$)。接下来是各个测试用例的描述。

每个测试用例由单行上的单个数字 $n$ ($1 \le n \le 1000$) 给出。

输出格式

对于每个测试用例，如果没有解，请在单独的一行中输出 “impossible”。否则，输出 $\frac{n(n+1)}{2}$ 行，包含骨牌的位置，按 $(1, 1), (1, 2), \dots$ 的顺序开始，并以 $(n, n)$ 骨牌的位置结束。每个位置应表示为四个整数 $x_1, y_1, x_2, y_2$ ($0 \le x_1, x_2, y_1, y_2 \le 10\,000\,000$)，其中 $(x_1, y_1)$ 是骨牌上较小数字所在的坐标，$(x_2, y_2)$ 是较大数字所在的坐标。

样例

输入 1

1
2

输出 1

1 1 1 2
1 3 1 4
1 5 1 6