在二维平面上有 $N$ 个点 $p_1, p_2, \dots, p_N$。

点 $p_i$ 位于 $(X_i, Y_i)$。没有两个点具有相同的坐标。

构造点序列 $p = (p_1, p_2, \dots, p_N)$ 的一个排列 $q = (q_1, q_2, \dots, q_N)$，使其满足以下条件，或者判断无解。

• 对于所有 $1 \le i \le N - 2$，这三个点 $q_i, q_{i+1}, q_{i+2}$ 依此顺序要么共线，要么形成一个逆时针转向。
  • 更具体地说，设 $q_i$ 的坐标为 $(x_i, y_i)$。则以下条件必须成立： $(x_{i+1} - x_i)(y_{i+2} - y_{i+1}) - (y_{i+1} - y_i)(x_{i+2} - x_{i+1}) \ge 0$。

请对 $T$ 组测试用例求解此问题。

输入格式

输入按以下格式给出：

T
case1
case2
:
caseT

每个测试用例按以下格式给出：

N
X1 Y1
X2 Y2
:
XN YN

数据范围

• $1 \le T \le 100$
• $3 \le N \le 3000$
• $0 \le X_i, Y_i \le 10^9$
• $(X_i, Y_i) \ne (X_j, Y_j)$ ($i \ne j$)
• 所有测试用例中 $N$ 的总和不超过 $3000$
• 所有输入值均为整数

输出格式

输出 $T$ 行。

对于第 $i$ 行，如果第 $i$ 个测试用例不存在满足条件的 $q$，则输出 -1。

否则，设 $q = (p_{r_1}, p_{r_2}, \dots, p_{r_N})$。按此顺序输出 $r_1, r_2, \dots, r_N$，中间用空格分隔。

如果存在多个合法答案，你可以输出其中任意一个。

样例

输入样例 1

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

输出样例 1

6 9 2 3 5 1 8 7 4

说明

图 1：样例解释。