Description

小s最近对数字情有独钟。他又发现了一种神奇的数字。对于数x，如果它二进制表示中只有一位是0，则x就会被小s所喜爱。比如5，二进制为101，则它被小s所喜爱。
现在，小s想知道，对于一个区间[L, R]，有多少数是他所喜爱的。

Format

Input

输入包含多组数据。
输入第一行T，表示数据组数。
每组数组仅有一行，包含两个正整数L, R。

Output

对于每组数据输出一行，表示答案。

Sample 1

Input

    2
5 10
2015 2015

Output

2
1

Limitation

1s, 256MKiB for each test case.
【数据范围与约定】
30%: L, R <= 10^6, T <= 10
60%: L, R <= 10^10, T <= 100
100%: L, R <= 10^18, T <= 10000