Вы путешествуете по живописному ландшафту, состоящему в основном из гор --- на вашем пути есть $n$ ориентиров (пики и долины). Вы останавливаетесь, чтобы перевести дух, и задаетесь вопросом: какую гору вы сейчас видите на горизонте? \includegraphics{https://static.eolymp.com/content/6d/6db0584145bbb05bdec7ef5840d57e6cf12f0142.gif} Вам дана полигональная цепочка $P_1P_2...P_n$ на плоскости. Координаты $x$ точек расположены в строго возрастающем порядке. Для каждого сегмента $P_iP_{i+1}$ этой цепочки найдите наименьший индекс $j > i$, для которого некоторая точка $P_jP_{j+1}$ видна из $P_iP_{i+1}$ (лежит строго над лучом $P_iP_{i+1}$). \InputFile Первая строка содержит количество тестов $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)$. \OutputFile Для каждого теста выведите одну строку, содержащую $n - 1$ целых чисел. Это должны быть наименьшие индексы сегментов цепочки, видимых справа, или $0$, если такой сегмент не существует.