Mountainous landscape

You travel through a landscape made mostly of mountains. There are $n$ landmarks, peaks and valleys, along your path. You stop to catch your breath and wonder which mountain you are looking at on the horizon.

Stated formally: you are given a polygonal chain $P_1 P_2 \dots P_n$ in the plane, and the $x$ coordinates of the points are strictly increasing. For each segment $P_i P_{i+1}$ of the chain, find the smallest index $j > i$ such that some point of $P_j P_{j+1}$ lies strictly above the ray that starts at $P_i$ and passes through $P_{i+1}$.

A point $Q = (x, y)$ lies strictly above the ray $P_i \to P_{i+1}$ when $x \ge x_{i+1}$ and $(x_{i+1} - x_i)(y - y_i) - (y_{i+1} - y_i)(x - x_i) > 0$.

The first line contains the number of test cases $T$. The test cases follow one after another.

The first line of each test case contains the number of vertices of the chain, $n$ ($2 \le n \le 100000$).

Each of the next $n$ lines contains the integer coordinates $x_i$ and $y_i$ of vertex $P_i$ ($0 \le x_1 < x_2 < \dots < x_n \le 10^9$, $0 \le y_i \le 10^9$).

For each test case, print one line with $n-1$ space separated integers. The $i$-th number is the smallest index of a chain segment visible to the right of segment $P_i P_{i+1}$, or 0 when no such segment exists.