Dağ mənzərəsi

Siz əsasən dağlardan ibarət mənzərəli bir landşaftda səyahət edirsiniz — yolunuzda $n$ ədəd oriyentir (zirvələr və dərələr) var. Siz nəfəsinizi dərmək üçün dayanırsınız və özünüzə sual verirsiniz: üfüqdə hansı dağı görürsünüz?

Sizə müstəvidə poliqonal zəncir $P_1{P}_2...P_n$ verilir. Nöqtələrin $x$ koordinatları ciddi artan qaydada yerləşdirilmişdir. Bu zəncirin hər bir seqmenti $P_i{P}_{i+1}$ üçün $j>i$ olan ən kiçik indeksi tapın ki, $P_j{P}_{j+1}$ seqmentinin bəzi nöqtəsi $P_i{P}_{i+1}$ seqmentindən görünür (şüanın $P_i{P}_{i+1}$ üzərində yerləşir).

Giriş verilənləri

Birinci sətir testlərin sayını $T$ ehtiva edir.

Hər bir testin birinci sətiri zəncirin $n(2\le n\le 10^5)$ ədəd zirvəsini ehtiva edən tam ədədi ehtiva edir. Növbəti $n$ sətirin hər biri $P_i(0\le x_1<x_2<...<x_n\le 10^9,0\le y_i\le 10^9)$ zirvəsinin tam ədədi koordinatları $x_i,y_i$ ehtiva edir.

Çıxış verilənləri

Hər bir test üçün sağdan görünən seqmentlərin ən kiçik indekslərini ehtiva edən bir sətir çıxarın, əgər belə bir seqment mövcud deyilsə $0$ yazın.

Nümunələr