첫 번째 등장 위치

유명한 Thue-Morse 수열은 무한 이진 수열 $T = t_0 t_1 t_2 \ldots$입니다. 음이 아닌 정수 $n$의 이진 표현에 1이 홀수 개 있으면 $t_n = 1$이고, 그렇지 않으면 $t_n = 0$입니다.

수열은 01101001100101101001011001101001...로 시작합니다.

수열의 부분 문자열 $t_{l..r} = t_l t_{l+1} \ldots t_r$을 생각해 봅시다. $t_{l..r}$이 $T$에서 처음 나타나는 인덱스를 구하세요. 즉, $t_{l..r} = t_{i..i+(r-l)}$을 만족하는 가장 작은 음이 아닌 정수 $i$를 찾으세요.

여러 테스트 케이스가 주어집니다. 첫 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 10^5$)가 주어집니다. 각 테스트 케이스는 한 줄로 이루어지며, 정수 $l$과 $r$ ($0 \le l \le r \le 10^{18}$)이 주어집니다.

각 테스트 케이스마다 $t_{l..r}$이 $T$에서 처음 나타나는 인덱스를 출력합니다.

첫 번째 예시에서 $t_{0..10}$은 분명히 인덱스 0에서 처음 나타납니다.

두 번째 예시에서 $t_{13..13}$ = 1은 인덱스 1에서 처음 나타납니다.

세 번째 예시에서 $t_{23..27}$ = 00110은 인덱스 5에서 처음 나타납니다.