Горный пейзаж

Вы путешествуете по живописному ландшафту, состоящему в основном из гор — на вашем пути есть $n$ ориентиров (пики и долины). Вы останавливаетесь, чтобы перевести дух, и задаетесь вопросом: какую гору вы сейчас видите на горизонте?

Вам дана полигональная цепочка $P_1{P}_2...P_n$ на плоскости. Координаты $x$ точек расположены в строго возрастающем порядке. Для каждого сегмента $P_i{P}_{i+1}$ этой цепочки найдите наименьший индекс $j>i$, для которого некоторая точка $P_j{P}_{j+1}$ видна из $P_i{P}_{i+1}$ (лежит строго над лучом $P_i{P}_{i+1}$).

Входные данные

Первая строка содержит количество тестов $T$.

Первая строка каждого теста содержит целое число $n(2\le n\le 10^5)$ — количество вершин на цепи. Каждая из следующих $n$ строк содержит целочисленные координаты $x_i,y_i$ вершины $P_i(0\le x_1<x_2<...<x_n\le 10^9,0\le y_i\le 10^9)$.

Выходные данные

Для каждого теста выведите одну строку, содержащую $n-1$ целых чисел. Это должны быть наименьшие индексы сегментов цепочки, видимых справа, или $0$, если такой сегмент не существует.

Примеры