Гірський пейзаж

Ви подорожуєте мальовничим ландшафтом, що складається переважно з гір — на вашому шляху є $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$, якщо такий сегмент не існує.

Приклади