Нещодавно перед будинком Лосяша впав метеорит. На наступний ранок Лосяш виявив, що у нього на клумбі виросла нова, невідома йому, рослина. Йшли дні, рослина рослі, і однієї ночі Лосяш побачив, що деякі її частини світяться.
А саме, рослина складається з великої кількості кульоподібних бульб, деякі з яких з'єднані стебельками. Після ретельного аналізу Лосяш встановив, що бульби з'єднані наступним чином - якщо співставити кожній бульбі номер, то бульба з номером один, яка відповідає коренб рослини, буде з'єднана з бульбою номер два, бальбаь два - з номерами один, три та чотири, а бульба i з номером більшим двох, з'єднана з i-1, якщо i непарне, або з i-2, i+1 та i+2 - якщо i парне.
Коли ж Лосяш став досліджувати закономірності світіння, то виявив, що якщо він доторкався до бульб з номерами u та v, то світитись починала бульба з мінімальним номером, яка знаходиться на найкоротшому щляху між u-ю та v-ю бульбами.
Так як поки що рослина Лосяша не дуже велика, то він попросив вас обчислити номер бульби, яка почне світитись, якщо він доторкнеться до бульб u та v.
У першому рядку вхідного файлу міститься одне ціле число n (1 ≤ n ≤ 100) - кількість пар бульб, цікавих Лосяшу. У наступних n рядках записано по два числа v_i та u_i (1 ≤ u_i, v_i ≤ 10^9, u_i ≠ v_i) - номери i-ї пари бульб.
У i-му рядку вихідного файлу виведіть номер бульби, яка почне світитись, якщо доторкнутись до бульб u_i та v_i.