Dağ mənzərəsi#7718
Siz əsasən dağlardan ibarət mənzərəli bir landşaftda səyahət edirsiniz — yolunuzda ə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_1P_2\dots P_n verilir. Nöqtələrin koordinatları ciddi artan qaydada yerləşdirilmişdir. Bu zəncirin hər bir seqmenti P_iP_{i+1} üçün j > i olan ən kiçik indeksi tapın ki, P_jP_{j+1} seqmentinin bəzi nöqtəsi P_iP_{i+1} seqmentindən görünür (şüanın P_iP_{i+1} üzərində yerləşir).
Birinci sətir testlərin sayını ehtiva edir.
Hər bir testin birinci sətiri zəncirin (2 \le n \le 10^5) ədəd zirvəsini ehtiva edən tam ədədi ehtiva edir. Növbəti sətirin hər biri P_i (0 \le x_1 < x_2 < \dots < x_n \le 10^9,\ 0 \le y_i \le 10^9) zirvəsinin tam ədədi koordinatları x_i,\ y_i ehtiva edir.
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ə yazın.
Nümunə 1