暂无测试数据。

道德经：“道生一，一生二，二生三，三生万物。”

以平凡情况入手，再从特殊到一般，是一种很常用的研究方法。从 $0$ 和 $1$ 到一切，是一种非常精妙的思路。

蒜头君最近发现，如果写成二进制，那么 $0_{10}=0_2$，$1_{10}=1_2$，而 $2_{10}=10_2$，于是他想到了一个巧妙的构造：

一个数字初始是 $1$，将数字写成二进制，把其中的 $0$ 变成 $1$，把 $1$ 变成 $2$，不断重复这一过程，重复无穷次。

前几次的过程是这样的：

$ 1_2 \to 10_2 \to 101_2 \to 10110_2 \to 10110101_2 $

现在蒜头君想要知道，经过无穷次这样的变换后，某个区间内有几个 $1$，你能帮帮他吗？

输入格式

第一行一个数 $n$，表示有 $n$ 个询问。

其后 $n$ 行，每行两个数 $a$ 和 $b$ （$n\le 5000$，$b\le 1e20$）。

输出格式

每行一个数，分别为第 $a$ 个数到第 $b$ 个数之间的 $1$ 的个数。

1
2 8

4