Лямбда-bitki
Son zamanlar Losyaşın evinin önünə bir meteorit düşdü. Ertəsi səhər Losyaş gördü ki, onun çiçək yatağında yeni, ona məlum olmayan bir bitki bitib. Günlər keçdi, bitki böyüdü və bir gecə Losyaş gördü ki, onun bəzi hissələri işıq saçır.
Bitki çox sayda kürə şəklində yumrulardan ibarətdir, bəziləri saplaqlarla birləşir. Dəqiq analizdən sonra Losyaş müəyyən etdi ki, yumrular aşağıdakı kimi birləşir: hər yumruya bir nömrə təyin etsək, bir nömrəli yumru, bitkinin kökü olan yumru, iki nömrəli yumru ilə birləşir. İki nömrəli yumru isə bir, üç və dörd nömrəli yumrularla birləşir. i nömrəli yumru isə iki nömrədən böyükdürsə, i-1 ilə birləşir, əgər i təkdirsə, ya da i-2, i+1 və i+2 ilə birləşir - əgər i cütdürsə.
Losyaş işıq saçma qanunauyğunluqlarını araşdırmağa başlayanda aşkar etdi ki, əgər o, u və v nömrəli yumrulara toxunarsa, u və v yumruları arasında ən qısa yolda olan ən kiçik nömrəli yumru işıq saçmağa başlayır.
Hələ ki, Losyaşın bitkisi çox böyük deyil, o, sizdən u və v yumrularına toxunarsa, işıq saçmağa başlayacaq yumrunun nömrəsini hesablamağı xahiş etdi.
Giriş verilənləri
Giriş faylının ilk sətirində bir tam ədəd n (1 ≤ n ≤ 100) - Losyaşın maraqlandığı yumru cütlərinin sayı verilir. Növbəti n sətirdə hər biri iki ədəd v_i və u_i (1 ≤ u_i, v_i ≤ 10^9, u_i ≠ v_i) - i-ci yumru cütünün nömrələri verilir.
Çıxış verilənləri
Çıxış faylının i-ci sətirində u_i və v_i yumrularına toxunulduqda işıq saçmağa başlayacaq yumrunun nömrəsini yazın.