24690번 - First Occurrence 다국어

The famous Thue-Morse sequence $T = t_0 t_1 t_2 \ldots$ is an infinite binary sequence that can be defined as follows: if the number of ones in the binary representation of $n$ is odd then $t_n = 1$, otherwise $t_n = 0$.

The sequence starts with 01101001100101101001011001101001...

Consider a substring of this sequence $t_{l..r} = t_l t_{l+1} \ldots t_r$. Find the index of the first occurrence of $t_{l..r}$ in $T$. In other words, find the smallest non-negative integer $i$ such that $t_{l..r} = t_{i..i+(r-l)}$.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

The only line of each test case contains two integers $l$ and $r$ ($0 \le l \le r \le 10^{18}$).

For each test case, print the index of the first occurrence of $t_{l..r}$ in $T$.

In the first example test case, $t_{0..10}$ obviously first occurs in $T$ at index $0$.

In the second example test case, $t_{13..13} = $ 1 first occurs in $T$ at index $1$.

In the third example test case, $t_{23..27} = $ 00110 first occurs in $T$ at index $5$.