산악 지형

산으로 이루어진 풍경을 지나며 여행한다. 경로에는 봉우리와 골짜기를 합쳐 $n$개의 지점이 있다. 잠시 숨을 고르면서, 지금 지평선 위로 보이는 산이 어느 것인지 궁금해졌다.

형식적으로 정리하면 이렇다. 평면 위의 꺾은선 $P_1 P_2 \dots P_n$이 주어지고, 각 점의 $x$좌표는 순증가한다. 꺾은선의 각 선분 $P_i P_{i+1}$에 대해, 선분 $P_j P_{j+1}$ 위의 어떤 점이 $P_i$에서 $P_{i+1}$ 방향으로 뻗는 반직선보다 엄밀히 위에 놓이는 가장 작은 인덱스 $j > i$를 구하라.

점 $Q = (x, y)$가 반직선 $P_i \to P_{i+1}$보다 엄밀히 위에 있다는 것은 $x \ge x_{i+1}$이면서 $(x_{i+1} - x_i)(y - y_i) - (y_{i+1} - y_i)(x - x_i) > 0$이라는 뜻이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 테스트 케이스가 하나씩 주어진다.

각 테스트 케이스의 첫 줄에는 꺾은선의 꼭짓점 개수 $n$이 주어진다 ($2 \le n \le 100000$).

다음 $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$개의 정수를 공백으로 구분해 한 줄에 출력한다. $i$번째 수는 선분 $P_i P_{i+1}$에서 오른쪽으로 보이는 선분 중 가장 작은 인덱스이고, 그런 선분이 없으면 0이다.