5694：BD String

众所周知，度度熊喜欢的字符只有两个：B和D。

今天，它发明了一种用B和D组成字符串的规则：

$S(1)=B$

$S(2)=BBD$

$S(3)=BBDBBDD$

…

$S(n)=S(n-1)+B+reverse(flip(S(n-1))$

其中，$reverse(s)$指将字符串翻转，比如$reverse(BBD)=DBB$，$flip(s)$指将字符串中的$B$替换为$D$，$D$替换为$B$，比如$flip(BBD)=DDB$。

虽然度度熊平常只用它的电脑玩连连看，这丝毫不妨碍这台机器无与伦比的运算速度，目前它已经算出了$S(2^{1000})$的内容，但度度熊毕竟只是只熊，一次读不完这么长的字符串。它现在想知道，这个字符串的第$L$位（从1开始）到第$R$位，含有的$B$的个数是多少？

第一行一个整数$T$，表示$T(1 \leq T \leq 1000)$ 组数据。

每组数据包含两个数$L$和$R(1 \leq L \leq R \leq 10^{18})$ 。

对于每组数据，输出$S(2^{1000})$表示的字符串的第$L$位到第$R$位中$B$的个数。