话说当初大闹天宫的猴头反斗精——孙悟空来到了21世纪。当他通过时空隧道来到21世纪时才发现世界发生了翻天覆地的变化。于是他决定来中国的泰山学艺。他在海南腾云驾雾来到泰山脚下，谁知脚下却有两个人把守。他走上前对他们说：“喂！我要见你们的师傅——粉面大秃驴。”那两个人没有搭理他，反而说：“我们的师傅岂是你这个毛猴想见就见的！”孙悟空听了，心中很是愤怒，心想：当初我大闹天宫时，怕过谁！而现在却让这两个毛孩训斥，哼！给你们点厉害瞧瞧。接着，他就掏出金箍棒朝那两个人砸去。可是谁知刚砸到他们面前，却被一道光给挡了回来。原来他们的面前都有一道防护层。“哼！21世纪还用武力解决问题，白痴！”他们不懈的说，“21世纪是智慧的时代，不过，看你是孙悟空的面子上，你只要答对我们的问题，我便放你进去见我们的师傅。”悟空听了，无奈的点了点头，看来只有这样了。“好，猴头，你听好了！这里有一个桃子，我们以下列的方式对它进行变换：
① 开始时，只有一个桃子；
② 每一次变换，把其中的桃子变成桃子和梨，其中的梨变成桃子。
我们用‘T’表示桃子，用‘L’表示梨，则经过无数次的变换，我们得到如下字符串“TLTTLTLTTLTTLTLTTLT……”。现在你的任务是：每次给你n个询问，每个询问为：在区间a和b之间有多少个桃子。”孙悟空听了傻了眼，他一个从石头里蹦出来的猴子，哪会这么多东西。可是他必须要去见泰山宗，怎么办呢？看来只有求助于你们了。
输入：
第一行是一个整数n，表示有n次提问，后面有n行，每行有两个整数a和b，用空格隔开。
输出：
共n行，每行有一个回答，表示在这个区间内有多少个桃子。
【样例】
输入 1
2 8
输出 4
【数据规模】
对于100%的数据
$ 1 \le n \le 5000$
$ 1\le a \le b \lt 2^{63}$