Лямбда-

Недавно перед домом Лосяша упал метеорит. На следующее утро Лосяш обнаружил, что в его палисаднике выросло новое, неизвестное ему, растение. Шли дни, растение росло, и однажды ночью Лосяш увидел, что некоторые его части светятся.

А именно, растение состоит из большого количества шарообразных клубней, некоторые из которых соединены стебельками. После тщательного анализа Лосяш установил, что клубни соединены следующим образом --- если сопоставить каждому клубню номер, то клубень с номером один, соответствующий корню растения, будет соединен с клубнем номер два, клубень два - с номерами один, три и четыре, а клубень $i$ с номером больше двух, соединен с $i - 1$, если $i$ нечетно, либо с $i - 2$, $i + 1$ и $i + 2$ --- если $i$ четно.

Когда же Лосяш стал исследовать закономерности свечения, то обнаружил, что если он дотрагивался до клубней с номерами $u$ и $v$, то светиться начинал клубень с минимальным номером, находящийся на кратчайшем пути между $u$-м и $v$-м клубнями.

Так как пока что растение Лосяша не очень большое, то он попросил вас вычислить номер клубня, который начнет светиться, если он дотронется до клубней $u$ и $v$.

В первой строке входного файла содержится одно целое число $n$ ($1 \le n \le 100$) --- количество пар клубней, интересных Лосяшу. В следующих $n$ строках записано по два числа $v_i$ и $u_i$ ($1 \le u_i, v_i \le 10^9, u_i \ne v_i$) --- номера $i$-й пары клубней.

В $i$-й строке выходного файла выведите номер клубня, который начнет светиться, если дотронуться до клубней $u_i$ и $v_i$.