UOJ Logo Universal Online Judge

UOJ

#525. 【美团杯2020】平行四边形

统计

蒜斜非常喜欢下围棋。自从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}$

下载

样例数据下载