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