Вы путешествуете по живописному ландшафту, состоящему в основном из гор — на вашем пути есть n ориентиров (пики и долины). Вы останавливаетесь, чтобы перевести дух, и задаетесь вопросом: какую гору вы сейчас видите на горизонте?
Вам дана полигональная цепочка P1P2...Pn на плоскости. Координаты x точек расположены в строго возрастающем порядке. Для каждого сегмента PiPi+1 этой цепочки найдите наименьший индекс j>i, для которого некоторая точка PjPj+1 видна из PiPi+1 (лежит строго над лучом PiPi+1).
Первая строка содержит количество тестов T.
Первая строка каждого теста содержит целое число n(2≤n≤105) — количество вершин на цепи. Каждая из следующих n строк содержит целочисленные координаты xi,yi вершины Pi(0≤x1<x2<...<xn≤109,0≤yi≤109).
Для каждого теста выведите одну строку, содержащую n−1 целых чисел. Это должны быть наименьшие индексы сегментов цепочки, видимых справа, или 0, если такой сегмент не существует.