蒜斜非常喜欢下围棋。自从AlphaOg面世以来，他就立志一定要研究出AlphaOg的破绽。 终于，他发现当AlphaOg遇到一种特殊局面后，它的神经网络会自动输出“投降”！

随着进一步的研究，蒜斜发现这种局面有着更一般的特性，不仅仅局限于固定大小棋盘。 具体来说，当棋盘大小是 $n$（$n+1$ 是一个质数）且棋盘上恰好有 $n$ 个棋子的时候，如果这些棋子的位置满足下列条件，那么 AlphaOg 就会直接投降。假设第 $i$ 个棋子的位置是点 $P_i$，处在第 $x_i$ 行第 $y_i$ 列，那么这些坐标需要满足：

1. $x_1$ 至 $x_n$ 是 $1 - n$ 的排列。
2. $y_1$ 至 $y_n$ 是 $1 - n$ 的排列。
3. 这些点之间不构成平行四边形（包括退化）。即对于任何两个不完全相同的棋子对 $(P_a, P_b), (P_c, P_d)$（允许它们之间共用至多一个棋子），线段 $P_aP_b$ 与 $P_cP_d$ 要么长度不同，要么所在的直线不平行且不重合。

凭借这项发现，蒜斜荣获了“北大算协吉祥物”的称号。 如果你也能找出一种合法方案，蒜斜的称号就是你的了！

输入格式

输入第一行包含一个整数 $t (1 \leq t \leq 10)$，表示数据组数。

对于每组数据，输入第一行包含一个整数 $n (4 \leq n \leq 1000)$，保证 $n+1$ 是一个质数。

输出格式

对于每组数据，如果无解输出一行一个整数 -1。否则输出 $n$ 行，每行两个整数 $(x_i, y_i) (1 \leq x_i \leq n, 1 \leq y_i \leq n)$，表示第 $i$ 个棋子的坐标。如果坐标方案不唯一，你只需要输出任意一种。

样例一

input

1
4

output

1 1
3 2
4 3
2 4

限制与约定

Small Task: $n \leq 12$。

Large Task: $n \leq 1000$。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载