Недавно перед домом Лосяша упал метеорит. На следующее утро Лосяш обнаружил, что в его палисаднике выросло новое, неизвестное ему, растение. Шли дни, растение росло, и однажды ночью Лосяш увидел, что некоторые его части светятся. А именно, растение состоит из большого количества шарообразных клубней, некоторые из которых соединены стебельками. После тщательного анализа Лосяш установил, что клубни соединены следующим образом - если сопоставить каждому клубню номер, то клубень с номером один, соответствующий корню растения, будет соединен с клубнем номер два, клубень два - с номерами один, три и четыре, а клубень \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}.