【美团杯2020】平行四边形

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

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

这些点之间不构成平行四边形（包括退化）即对于任何两个不完全相同的棋子对 (Pa,Pb),(Pc,Pd)（允许它们之间共用至多一个棋子），线段 PaPb 与 PcPd 要么长度不同要么所在的直线不平行且不重合。
凭借这项发现蒜斜荣获了“北大算协吉祥物”的称号。 如果你也能找出一种合法方案蒜斜的称号就是你的了！

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

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

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

一个n*n棋盘(n+1为奇质数)每行和每列有且只有一个棋子，且没有四个棋子可以构成一个平行四边形求任意一组解

• 如果m为奇质数一定存在模m的.
• 原根的求法：如果g是m的原根，gⁱ = 1 (mod m)当且仅当i=m-1的时候成立
• 四个点构成平行四边形当且仅当满足以下两个条件
• 根据原根嘚性质，当a!=c时g^a!=g^c,结论和假设矛盾
• 所以就证明了不会构成平行四边形