你正行走在一段主要由山脉组成的风景区中——你的路径上有 $n$ 个地标（山峰和山谷）。你停下来喘口气，不禁好奇：在地平线上你当前能看到哪座山？

形式化地，给定平面上的一个折线 $P_1P_2 \dots P_n$。这些点的 $x$ 坐标严格递增。对于该折线的每一段 $P_iP_{i+1}$，请找到最小的索引 $j > i$，使得 $P_jP_{j+1}$ 上至少有一点从 $P_iP_{i+1}$ 是可见的（即位于射线 $\vec{P_iP_{i+1}}$ 的严格上方）。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述： 每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示折线上的顶点数。 接下来的 $n$ 行，每行包含顶点 $P_i$ 的整数坐标 $x_i, y_i$ ($0 \le x_1 < x_2 < \dots < x_n \le 10^9$; $0 \le y_i \le 10^9$)。

输出格式

对于每个测试用例，输出一行，包含 $n-1$ 个由空格分隔的整数。这些整数表示向右可见的最小折线段索引，如果不存在这样的线段，则输出 $0$。

样例

输入 1

2
8
0 0
3 7
6 2
9 4
11 2
13 3
17 13
20 7
7
0 2
1 2
3 1
4 0
5 2
6 1
7 3

输出 1

0 3 6 5 6 0 0
6 4 4 0 6 0