数字精灵

题目描述

两个数字精灵团队进行友谊赛，每个小精灵的攻击力和防御力相同，都是它表示的正整数N转化为二进制后末尾连续0的数量。

甲队优先派出一个数字i进行攻击，乙队采取的防御策略是选择i+2迎战。

比赛进行了T轮，每一轮都会给定一个范围[l,r]，甲乙两队按照既定策略进行攻防，本着友谊第一的理念，甲队在选择数字的时候保证乙队有合乎策略的数字可选，请问每一轮比赛中有多少种可能乙队能够抵挡甲队的攻击(防御力>攻击力)?

例如给定范围[4,6],甲队只能选择4，转为二进制100,攻击力为2，乙队只能选择6，转化为二进制110,防御力为1，所以乙队防守失败，防守成功有0种情况。

输入描述

输入T+1 行，第一行一个整数T，表示比赛轮数。

第2行到T+1行，每行两个正整数表示区间端点l,r。

输出描述

输出T行，每行一个整数表示满足条件的情况数量。 样例1

输入

2

3 5

15 20

输出

1

3

对于前10%的测试数据，r=l+2;

对于前30%的测试数据，1<r<10^3;

对于前80%的测试数据，1<r<10^6;

对于100%的测试数据，T≤10^5,1≤1≤r-2≤10^18。