UOJ Logo Universal Online Judge

UOJ

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

附件下载 统计

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

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

  1. x1xn1n 的排列。
  2. y1yn1n 的排列。
  3. 这些点之间不构成平行四边形(包括退化)。即对于任何两个不完全相同的棋子对 (Pa,Pb),(Pc,Pd)(允许它们之间共用至多一个棋子),线段 PaPbPcPd 要么长度不同,要么所在的直线不平行且不重合。

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

输入格式

输入第一行包含一个整数 t(1t10),表示数据组数。

对于每组数据,输入第一行包含一个整数 n(4n1000),保证 n+1 是一个质数。

输出格式

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

样例一

input

1
4

output

1 1
3 2
4 3
2 4

限制与约定

Small Task: n12

Large Task: n1000

时间限制:1s

空间限制:512MB

下载

样例数据下载