람다

얼마 전 로샤의 집 앞에 운석이 떨어졌다. 다음 날 아침 로샤는 자기 정원에서 처음 보는 식물이 자란 것을 발견했다. 식물은 계속 자랐고, 어느 날 밤 로샤는 식물의 일부가 빛나는 것을 보았다.

이 식물은 구형 덩이줄기가 많이 모여 있으며, 그중 일부는 줄기로 연결되어 있다. 자세히 분석한 로샤는 덩이줄기가 다음과 같이 연결되어 있다는 것을 알아냈다. 각 덩이줄기에 번호를 붙이면, 뿌리에 해당하는 1번 덩이줄기는 2번 덩이줄기와 연결된다. 2번 덩이줄기는 1번, 3번, 4번 덩이줄기와 연결된다. 번호가 2보다 큰 덩이줄기 $i$는 $i$가 홀수이면 $i - 1$번과 연결되고, $i$가 짝수이면 $i - 2$번, $i + 1$번, $i + 2$번과 연결된다.

로샤는 빛나는 규칙도 연구했다. 덩이줄기 $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$를 건드렸을 때 빛나기 시작하는 덩이줄기의 번호를 출력한다.