Нещодавно перед будинком Лосяша впав метеорит. На наступний ранок Лосяш виявив, що у нього на клумбі виросла нова, невідома йому, рослина. Йшли дні, рослина рослі, і однієї ночі Лосяш побачив, що деякі її частини світяться. А саме, рослина складається з великої кількості кульоподібних бульб, деякі з яких з'єднані стебельками. Після ретельного аналізу Лосяш встановив, що бульби з'єднані наступним чином - якщо співставити кожній бульбі номер, то бульба з номером один, яка відповідає коренб рослини, буде з'єднана з бульбою номер два, бальбаь два - з номерами один, три та чотири, а бульба \textbf{i} з номером більшим двох, з'єднана з \textbf{i-1}, якщо \textbf{i} непарне, або з \textbf{i-2}, \textbf{i+1} та \textbf{i+2} - якщо \textbf{i} парне. \includegraphics{https://static.e-olymp.com/content/7c/7cfd8651b5b6df35cae21ea30fd9fca406b87ccf.jpg} Коли ж Лосяш став досліджувати закономірності світіння, то виявив, що якщо він доторкався до бульб з номерами \textbf{u} та \textbf{v}, то світитись починала бульба з мінімальним номером, яка знаходиться на найкоротшому щляху між \textbf{u}-ю та \textbf{v}-ю бульбами. Так як поки що рослина Лосяша не дуже велика, то він попросив вас обчислити номер бульби, яка почне світитись, якщо він доторкнеться до бульб \textbf{u} та \textbf{v}. \InputFile У першому рядку вхідного файлу міститься одне ціле число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}) - кількість пар бульб, цікавих Лосяшу. У наступних \textbf{n} рядках записано по два числа \textbf{v_i} та \textbf{u_i} (\textbf{1} ≤ \textbf{u_i}, \textbf{v_i} ≤ \textbf{10^9}, \textbf{u_i} ≠ \textbf{v_i}) - номери \textbf{i}-ї пари бульб. \OutputFile У \textbf{i}-му рядку вихідного файлу виведіть номер бульби, яка почне світитись, якщо доторкнутись до бульб \textbf{u_i} та \textbf{v_i}.